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); }