Submission #1269234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269234		BuzzyBeez	Chessboard (IZhO18_chessboard)	C++20	100 / 100	159 ms	2736 KiB

chessboard

#include <bits/allocator.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2")
#include <bits/stdc++.h> 
using namespace std;
#define taskname "default"

bool mode;
// mode = 0: (1, 1) = black 
// mode = 1: (1, 1) = white

int n; long long sz;
array<int, 4> rect[100008];
int pfr[100008], pfc[100008];

void build(int m) {
	for (int i = 1; i <= n; ++i) {
		pfr[i] = pfr[i - 1] + ((((i - 1) / sz) & 1) ^ m ? -1 : +1);
		pfc[i] = pfc[i - 1] + ((((i - 1) / sz) & 1) ? -1 : +1);
	}
}

long long query(int x1, int y1, int x2, int y2) {
	return (1LL * (x2 - x1 + 1) * (y2 - y1 + 1) + 1LL * (pfr[x2] - pfr[x1 - 1]) * (pfc[y2] - pfc[y1 - 1])) / 2;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int m; cin >> n >> m;
	long long tot = 0, expected, same, edit_dist, ans = 1LL * n * n;
	for (int i = 1; i <= m; ++i) {
		cin >> rect[i][0] >> rect[i][1] >> rect[i][2] >> rect[i][3];
		tot += 1LL * (rect[i][2] - rect[i][0] + 1) * (rect[i][3] - rect[i][1] + 1);
	}
	vector<int> divs;
	for (int d = 1; d < n; ++d) if (n % d == 0) {
		divs.push_back(d);
	}
	for (int d : divs) {
		sz = d; 
		mode = 0; same = 0; build(mode);
		expected = sz * sz * ((1LL * (n / sz) * (n / sz) + 1 - mode) / 2);
		for (int i = 1; i <= m; ++i) 
			same += query(rect[i][0], rect[i][1], rect[i][2], rect[i][3]);
		edit_dist = tot - same + expected - same;
		ans = min(ans, edit_dist);
		same = 0; mode = 1; build(mode);
		expected = sz * sz * ((1LL * (n / sz) * (n / sz) + 1 - mode) / 2);
		for (int i = 1; i <= m; ++i) 
			same += query(rect[i][0], rect[i][1], rect[i][2], rect[i][3]);
		edit_dist = tot - same + expected - same;
		ans = min(ans, edit_dist);
	}
	cout << ans;
}

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