Submission #505815

#	Time	Username	Problem	Language	Result	Execution time	Memory
505815		Mazaalai	Chessboard (IZhO18_chessboard)	C++17	70 / 100	178 ms	2676 KiB

chessboard

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
using ll = long long;
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;
}
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 a, b; cin >> a >> b >> a >> b;
		// cout << a << " " << b << ": ";
		for (auto& num : divs) {
			int col = ((a + num - 1) / num + (b + num - 1) / num)&1; // 0 ? black : white
			// cout << num << ',' << col << ' ';
			dp[num] += col == 1 ? 1 : -1;
		}
		// cout << '\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: 0 / 30