lessons/参考实现/07-二分图/AtCoder-agc025_d.cpp

#include <bits/stdc++.h>
using namespace std;

int color_for_distance(int x, int y, int distance_squared) {
    while (distance_squared % 4 == 0) {
        distance_squared /= 4;
        x /= 2;
        y /= 2;
    }
    if (distance_squared & 1) return (x + y) & 1;
    return x & 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, d1, d2;
    cin >> n >> d1 >> d2;
    vector<vector<pair<int, int>>> bucket(4);
    for (int x = 0; x < 2 * n; ++x) {
        for (int y = 0; y < 2 * n; ++y) {
            int key = 2 * color_for_distance(x, y, d1)
                    + color_for_distance(x, y, d2);
            bucket[key].push_back({x, y});
        }
    }
    auto best = max_element(bucket.begin(), bucket.end(),
                            [](const auto &a, const auto &b) { return a.size() < b.size(); });
    for (int i = 0; i < n * n; ++i) {
        cout << (*best)[i].first << ' ' << (*best)[i].second << '\n';
    }
    return 0;
}