Submission #378566

#	Time	Username	Problem	Language	Result	Execution time	Memory
378566		rk42745417	Chessboard (IZhO18_chessboard)	C++17	47 / 100	133 ms	262148 KiB

chessboard

#include <bits/stdc++.h>
using namespace std;

using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll LINF = 2e18;
const double EPS = 1e-9;
#define EMT ios::sync_with_stdio(0); cin.tie(0);

bool prime_test(int n) {
	for(int i = 2; i < n; i++)
		if(n % i == 0)
			return false;
	return true;
}
void solve(int n) {
	int k;
	cin >> k;
	vector<vector<int>> sum(n + 1, vector<int>(n + 1));
	for(int i = 0, a, b, c, d; i < k; i++) {
		cin >> a >> b >> c >> d;
		sum[a][b]++;
	}
	for(int i = 1; i <= n; i++)
		for(int j = 1, g = 0; j <= n; j++)
			g += sum[i][j], sum[i][j] = sum[i - 1][j] + g;
	//for(int i = 1; i <= n; i++)
		//for(int j = 1; j <= n; j++)
			//cout << sum[i][j] << " \n"[j == n];
	int ans = INF;
	for(int i = 1; i < n; i++) {
		if(n % i)
			continue;
		int res = 0, w = n / i;
		for(int j = 1; j <= w; j ++) {
			for(int k = 1; k <= w; k++) {
				if((j + k) & 1) {
					res += sum[j * i][k * i] - sum[j * i - i][k * i] - sum[j * i][k * i - i] + sum[j * i - i][k * i - i];
				}
				else {
					res += i * i - (sum[j * i][k * i] - sum[j * i - i][k * i] - sum[j * i][k * i - i] + sum[j * i - i][k * i - i]);
				}
			}
		}
		//cout << i << ' ' << res << ' ' << n * n - res << '\n';
		ans = min({ans, res, n * n - res});
	}
	cout << ans << '\n';
}
void solve_2(int n) {
	int cnt[2] = {0}, k;
	cin >> k;
	for(int i = 0, a, b, c, d; i < k; i++) {
		cin >> a >> b >> c >> d;
		cnt[(a + b) % 2]++;
	}
	ll a = 1LL * n * n / 2, b = 1LL * n * n - a;
	cout << min(cnt[1] + b - cnt[0], cnt[0] + a - cnt[1]) << '\n';
}
signed main() { EMT
	int n;
	cin >> n;
	if(prime_test(n))
		solve_2(n);
	else
		solve(n);
}
/*
6 8
3 3 3 3
1 2 1 2
3 4 3 4
5 5 5 5
4 3 4 3
4 4 4 4
2 1 2 1
3 6 3 6

*/

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