Divide Points [Good Bye 2019 E]

https://codeforces.com/contest/1270/problem/E

解説

https://codeforces.com/contest/1270/submission/67941885

順位表を見ると、みんな爆速で通しているので、なにか特殊なルールで分けるのだろうというのは分かる。
ヤバい状況を考えるというのが抜けていた。
今回のヤバ状況は、全部のグリッドに点がある場合である。
この場合は(x + y) % 2で、塗り分ければ問題ない。
これは使えそう。

だが、サンプル2でそれをやると、全部同じ色になってしまうので、それでは困る。
拡大縮小、回転、平行移動をしてもマンハッタン距離の大小関係は変わらないので、それを上手く使う。
以下、chokudaiさんの解法を参考に書いた調整手段。
x+yのパリティが全部1の場合はx座標を+1して、全部0にしておこう。
この状態で45度回転を行って、2分の1に縮小する。
パリティが0なので、2分の1に縮小しても切り捨てにならない。
これを2グループに分かれるまで繰り返す。

int N, X[1010], Y[1010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> X[i] >> Y[i];

    vector<int> a, b;
    do {
        a.clear();
        b.clear();

        rep(i, 0, N) {
            if ((X[i] + Y[i]) % 2 == 0) a.push_back(i);
            else b.push_back(i);
        }

        if (a.size() == 0) rep(i, 0, N) X[i]++;

        rep(i, 0, N) {
            int x = (X[i] + Y[i]) / 2;
            int y = (X[i] - Y[i]) / 2;
            X[i] = x;
            Y[i] = y;
        }
    } while (a.size() * b.size() == 0);

    int n = a.size();
    printf("%d\n", n);
    fore(i, a) i++;
    outv(a);
}