Submission #505879

#	Time	Username	Problem	Language	Result	Execution time	Memory
505879		Mazaalai	Chessboard (IZhO18_chessboard)	C++17	100 / 100	636 ms	2800 KiB

chessboard

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
using ll = long long;
using PII = pair <int, int>;
const ll INF = 1e18;
const int N = 1e5 + 5;
ll n, m, ans = INF;
vector <int> divs;
ll dp[N];
void add(int num) {
	if (num == n) return;
	divs.pb(num);
	ll len = n / num;
	dp[num] = (len * len + 1) / 2 * num * num;
}
int getCnt(int pos, int len) {
	int full = pos - (pos % len);
	int ret = (full / len + 1) / 2 * len;
	if ((full / len) % 2 == 0) ret += pos - full;
	return ret;
}
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	cin >> n >> m;
	for (int i = 1; i * i <= n; i++) {
		if (n % i != 0) continue;
		add(i);
		if (i * i != n) add(n / i);
	}
	for (int i = 0; i < m; i++) {
		int a1, b1, a2, b2; cin >> a1 >> b1 >> a2 >> b2;
		for (auto& num : divs) {
			int black, white, Black, White;
			black = getCnt(a2, num) - getCnt(a1-1, num);
			white = a2 - a1 + 1 - black;
			Black = getCnt(b2, num) - getCnt(b1-1, num);
			White = b2 - b1 + 1 - Black;
			ll cur = black - white, cur1 = -cur;
			dp[num] -= cur * Black + cur1 * White;
			// cout << a1 << ' ' << b1 << ' ' << num << " : " << cur * Black + cur1 * White << '\n';
		}
	}
	for (auto& num : divs) {
		// cout << num << ": " << dp[num] << '\n';
		ans = min(ans, min(dp[num], n * n - dp[num]));
	}
	cout << ans << '\n';
}

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