Submission #41171

#	Time	Username	Problem	Language	Result	Execution time	Memory
41171		aome	Chessboard (IZhO18_chessboard)	C++14	100 / 100	551 ms	104812 KiB

chessboard

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

struct Rec {
	int x1, y1, x2, y2;
} rec[N];

int n, m;
long long res = 1e18;

void cal(int x, int l, int r, int *cnt) {
	cnt[0] = cnt[1] = 0;
	if (l / x != r / x) {
		cnt[0] += ( (r / x - 1) / 2 - l / x / 2 ) * x;
		if (r / x % 2 == 0) cnt[0] += r - r / x * x + 1;
		if (l / x % 2 == 0) cnt[0] += (l / x + 1) * x - l;
	}
	else {
		if (l / x % 2 == 0) cnt[0] += r - l + 1;
	}
	cnt[1] = r - l + 1 - cnt[0];
	// cout << "# " << cnt[0] << ' ' << cnt[1] << '\n';
}

void solve(int fix) {
	long long val1 = 0, val2 = 0;
	// change all white -> black
	val1 = 1LL * (n / fix) * (n / fix) / 2 * fix * fix;
	val2 = 1LL * n * n - val1;
	// cout << "#val " << val1 << ' ' << val2 << '\n';
	for (int i = 1; i <= m; ++i) {
		int cntx[2], cnty[2];
		// cout << "#X\n";
		cal(fix, rec[i].x1, rec[i].x2, cntx);
		// cout << "#Y\n";
		cal(fix, rec[i].y1, rec[i].y2, cnty);
		val1 += 1LL * cntx[0] * cnty[0] + 1LL * cntx[1] * cnty[1]; // black -> white
		val1 -= 1LL * cntx[0] * cnty[1] + 1LL * cntx[1] * cnty[0]; // black -> black
		val2 += 1LL * cntx[0] * cnty[1] + 1LL * cntx[1] * cnty[0]; // black -> white
		val2 -= 1LL * cntx[0] * cnty[0] + 1LL * cntx[1] * cnty[1]; // black -> black
	}
	// cout << "#at " << fix << ' ' << val1 << ' ' << val2 << '\n'; 
	res = min(res, min(val1, val2));
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		cin >> rec[i].x1 >> rec[i].y1 >> rec[i].x2 >> rec[i].y2;
		rec[i].x1--, rec[i].x2--, rec[i].y1--, rec[i].y2--;
	}
	// solve(2);
	for (int i = 1; i < n; ++i) {
		if (n % i == 0) solve(i);
	}
	cout << res;
}

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