Submission #1129413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129413		Tsagana	Chessboard (IZhO18_chessboard)	C++17	100 / 100	459 ms	444 KiB

chessboard

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define aint(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

vector<int> di = {1};
int dif[200005];

int find(int x, int d){
	return x / (2 * d) * d + min(x % (2 * d), d);
}

void solve () {
	int n, k; cin >> n >> k;
	for (int i = 2; i * i <= n; i++) {
		if (n % i != 0) continue ;
		di.pb(i);
		if (i * i != n) di.pb(n / i);
	}
	
	for (int i = 0; i < di.size(); i++)
		dif[i] = n * n - n * n / (di[i] * di[i]) / 2 * (di[i] * di[i]);
	
	int ox, oy, ex, ey;
	while (k--) {
		int x1, x2, y1, y2; cin >> x1 >> y1 >> x2 >> y2; x1--; y1--;
		for (int i = 0; i < di.size(); i++){
			ex = find(x2, di[i]) - find(x1, di[i]);
			ox = x2 - x1 - ex;
			ey = find(y2, di[i]) - find(y1, di[i]);
			oy = y2 - y1 - ey;
			dif[i] += ex * oy + ey * ox - ex * ey - ox * oy;
		}
	}

	int ans = 1e12;
	for (int i = 0; i < di.size(); i++) ans = min(ans, min(dif[i], n * n - dif[i]));
	cout << ans;
}
signed main() {IOS solve(); return 0;}

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