闲话：做这场的 B 用时跟 C 差不多
不会直接构造，因此这是一个无脑做法。
考虑对于 \(\forall x \in [1, n], y \in [1, m], (x + 3y, 3x + y)\) 看成一个点，那么选择的 \((x, y)\) 要满足，不存在一行或一列有超过 \(1\) 个点。
这启发我们对于合法的点 \((a, b)\)，行和列连边，即 \(a \to b\)，那么就是要构造出这个二分图的一个最大匹配。
考察合法的连边，\(a, b\) 应满足什么条件。不难推出：
- \(8 \mid (3a - b)\)；
- \(\max(3a - 8m, \frac{a + 8}{3}) \le b \le \min(3a - 8, \frac{8n + a}{3})\)。
所以如果知道了 \(a\)，那么 \(a\) 连出去的 \(b\) 模 \(8\) 都相等，并且在所有模 \(8\) 与它相等的数中是一段区间。
因为 \(a\) 有 \(O(n + m)\) 个，所以直接枚举 \(a\)，贪心取出最小的满足要求的 \(b\)，即可构造。实现时可以开 \(8\) 个 set。
时间复杂度 \(O((n + m) \log (n + m))\)。
code
// Problem: C - One Three Nine
// Contest: AtCoder - AtCoder Regular Contest 139
// URL: https://atcoder.jp/contests/arc139/tasks/arc139_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 1000100;
ll n, m;
set<ll> S[8];
void solve() {
scanf("%lld%lld", &n, &m);
for (ll y = 4; y <= n * 3 + m; ++y) {
S[y % 8].insert(y);
}
for (int i = 0; i < 8; ++i) {
S[i].insert(-1e9);
S[i].insert(1e9);
}
vector<pii> vc;
for (ll a = 4; a <= n + m * 3; ++a) {
ll l = max(3 * a - m * 8, (a + 10) / 3), r = min(3 * a - 8, (8 * n + a) / 3);
if (l > r) {
continue;
}
ll b = *S[3 * a % 8].lower_bound(l);
if (b > r) {
continue;
}
// printf("%lld %lld\n", a, b);
ll x = (3 * b - a) / 8, y = (3 * a - b) / 8;
vc.pb(x, y);
S[3 * a % 8].erase(b);
}
printf("%d\n", (int)vc.size());
for (pii p : vc) {
printf("%lld %lld\n", p.fst, p.scd);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}