Submission #501866

#	Time	Username	Problem	Language	Result	Execution time	Memory
501866		NachoLibre	Chessboard (IZhO18_chessboard)	C++17	100 / 100	839 ms	4488 KiB

chessboard

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;

ll Fw(ll n, ll m, int w) {
	return n / w * m / w / 2 * w * w;
}
ll Fb(ll n, ll m, int w) {
	return n * m - Fw(n, m, w);
}
ll B(ll n, ll m, int w, int x = 0, int y = 0) {
	if(x / w + y / w & 1)
	return Fb(n, m, w);
	return Fw(n, m, w);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	#ifdef wambule
	freopen("untitledfile.txt", "r", stdin);
	#endif
	ll n;
	int k;
	cin >> n >> k;
	vector<array<int, 4>> v;
	for(int i = 0; i < k; ++i) {
		array<int, 4> x;
		cin >> x[0] >> x[2] >> x[1] >> x[3];
		x[0] -= 1; x[1] -= 1;
		x[2] -= 1; x[3] -= 1;
		v.push_back(x);
	}
	vector<int> d{1};
	for(int i = 2; i * i <= n; ++i) {
		if(n % i == 0) {
			d.push_back(i);
			if(i * i ^ n) d.push_back(n / i);
		}
	}
	ll fp = n * n;
	for(int w : d) {
		ll ap = B(n, n, w);
		// cout << w << " -0- " << ap << endl;
		for(auto y : v) {
			array<int, 4> x;
			x[0] = y[0] / w * w;
			x[2] = y[2] / w * w;
			x[1] = y[1] / w * w + w - 1;
			x[3] = y[3] / w * w + w - 1;
			ll xn = x[1] - x[0] + 1;
			ll xm = x[3] - x[2] + 1;
			ll tp = B(xn, xm, w, x[0], x[2]);

			tp -= B(w, xm, w, x[0], x[2]) / w * (y[0] - x[0]);
			tp -= B(w, xm, w, x[1] + 1 - w, x[2]) / w * (x[1] - y[1]);
			tp -= B(xn, w, w, x[0], x[2]) / w * (y[2] - x[2]);
			tp -= B(xn, w, w, x[0], x[3] + 1 - w) / w * (x[3] - y[3]);

			tp += B(w, w, w, x[0], x[2]) / w / w * (y[2] - x[2]) * (y[0] - x[0]);
			tp += B(w, w, w, x[0], x[3] + 1 - w) / w / w * (x[3] - y[3]) * (y[0] - x[0]);
			tp += B(w, w, w, x[1] + 1 - w, x[3] + 1 - w) / w / w * (x[3] - y[3]) * (x[1] - y[1]);
			tp += B(w, w, w, x[1] + 1 - w, x[2]) / w / w * (y[2] - x[2]) * (x[1] - y[1]);

			ap -= tp;
			ap += 1ll * (y[1] - y[0] + 1) * (y[3] - y[2] + 1) - tp;

			// cout << w << "\n";
			// cout << y[0] << " " << y[1] << " " << y[2] << " " << y[3] << "\n";
			// cout << x[0] << " " << x[1] << " " << x[2] << " " << x[3] << "\n";
			// cout << tp << "\n\n";
		}
		// cout << w << " -1- " << ap << endl;
		fp = min(fp, min(ap, n * n - ap));
	}
	cout << fp << endl;
	return 0;
}

Compilation message (stderr)

chessboard.cpp: In function 'long long int B(long long int, long long int, int, int, int)':
chessboard.cpp:15:11: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   15 |  if(x / w + y / w & 1)
      |     ~~~~~~^~~~~~~

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