Submission #377600

#	Time	Username	Problem	Language	Result	Execution time	Memory
377600		SeDunion	Chessboard (IZhO18_chessboard)	C++17	23 / 100	2087 ms	1516 KiB

chessboard

#include<bits/stdc++.h>
#ifndef LOCAL
#define cerr if(false)cerr
#endif // LOCAL
using namespace std;
using ll = long long;
const int N = 1e6 + 66;

#define y1 slkdjflkjsdlfkjlskjfjklkdjslfjslkdjflkjlsdkjflkjslkdjflkdslfkjsldklkjsdjfntnfj
#define y0 alsjdljrktnmndfdfgjhkjhdkfjgbtnmbmfhkjgdkjfhkjxhkjhgtgbhhdjbhjhtdbjbhjhtbhbgbb

int x0[N], y0[N], x1[N], y1[N], n, k;

ll cnt(int d, int x, int y) {
	if (x < 0 || y < 0) return 0;
	int X = x / d, Y = y / d;
	//if (0) {
		ll cur = 0;
		for (int i = 0 ; i < X * d ; ++ i) {
			for (int j = 0 ; j < Y * d ; ++ j) {
				if ((i / d + j / d) % 2 == 0) cur++;
			}
		}
		//return cur;
	//}
	cerr << d << " : " << x << " " << y << " " << X << " " << Y << endl;
	//ll cur = (X * 1ll * Y + 1) / 2;
	ll Xc = Y % 2 == 1 ? X / 2 : (X + 1) / 2;
	ll Yc = X % 2 == 1 ? Y / 2 : (Y + 1) / 2;
	cur += Xc * d * (y - Y * d + 1);
	cur += Yc * d * (x - X * d + 1);
	if ((X + Y) % 2 == 0)
		cur += (x - X * d + 1) * 1ll * (y - Y * d + 1);
	return cur;
}

ll solve(int d) {
	ll cur = cnt(d, n-1, n-1);
	for (int i = 0 ; i < k ; ++ i) {
		ll black = cnt(d, x1[i], y1[i]) - cnt(d, x0[i] - 1, y1[i]) - cnt(d, x1[i], y0[i] - 1) + cnt(d, x0[i] - 1, y0[i] - 1);
		ll area = (y1[i] - y0[i] + 1) * 1ll * (x1[i] - x0[i] + 1);
		//cerr << d << " " << black << " " << area << " d/black/area\n";
		cur += area - black * 2;
	}
	return cur;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> k;
	for (int i = 0 ; i < k ; ++ i) {
		cin >> x0[i] >> y0[i] >> x1[i] >> y1[i];
		x0[i]--, y0[i]--, x1[i]--, y1[i]--;
	}
	ll ans = n * 1ll * n;
	for (int d = 1 ; d < n ; ++ d) {
		if (n % d == 0) {
			for (int i = 0 ; i < n ; ++ i) {
				for (int j = 0 ; j < n ; ++ j) {
					if ((i / d + j / d) % 2 == 0) cerr << "X";
					else cerr << ".";
				}
				cerr << "\n";
			}
			cerr << "\n";
			ll cur = solve(d);
			ans = min(ans, min(cur, n * 1ll * n - cur));
		}
	}
	cout << ans;
}

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:61:9: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   61 |      if ((i / d + j / d) % 2 == 0) cerr << "X";
      |         ^

• Subtask 1: 8 / 8
• Subtask 2: 0 / 8
• Subtask 3: 15 / 15
• Subtask 4: 0 / 16
• Subtask 5: 0 / 23
• Subtask 6: 0 / 30