Submission #380648

#	Time	Username	Problem	Language	Result	Execution time	Memory
380648		Fireball0424	Chessboard (IZhO18_chessboard)	C++14	100 / 100	840 ms	5868 KiB

chessboard

#include <bits/stdc++.h>
#define int long long 
#define INF INT_MAX
#define ld long double
#define fr first
#define sc second
using namespace std;
 
struct rec{
	int x1, y1, x2, y2;
};
 
void solve(){
	int n, k;
	cin >> n >> k;
	vector<rec> v(k);
	for(int i = 0; i < k; i++){
		cin >> v[i].x1 >> v[i].y1 >> v[i].x2 >> v[i].y2; 
	}
	auto cal = [&](int x, int y, int len){
		int sum[4] = {};
		int res = 0, tx = x % len, ty = y % len;
		sum[0] = (x / len) * (y / len) / 2 * len * len;
        if((x % (2 * len)) < len) sum[1] = tx * ((y / len) / 2) * len;
        else sum[1] = tx * ((y / len + 1) / 2) * len;
        if((y % (2 * len)) < len) sum[2] = ty * ((x / len) / 2) * len;
        else sum[2] = ty * ((x / len + 1) / 2) * len;
        if((x % (2 * len) < len) != (y % (2 * len) < len)) sum[3] = tx * ty;
		for(int i = 0; i < 4; i++) res += sum[i];
		return res;
	};
	int mn = n * n;
	for(int i = 1; i < n; i++){
		if(n % i != 0) continue;
		int sum[3] = {};
		for(auto j : v){
			int x1 = j.x1, x2 = j.x2, y1 = j.y1, y2 = j.y2;
			int tmp = cal(x2, y2, i) - cal(x2, y1 - 1, i) - cal(x1 - 1, y2, i) + cal(x1 - 1, y1 - 1, i);
			sum[0] += tmp; // cal black
			sum[1] += (x2 - x1 + 1) * (y2 - y1 + 1) - tmp; // cal white
		}
		sum[2] = cal(n, n, i) - sum[0];
		mn = min(mn, sum[1] + sum[2]);
		mn = min(mn, n * n - sum[1] - sum[2]);
	}
	cout << mn;
}
 
main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
}

Compilation message (stderr)

chessboard.cpp:49:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   49 | main(){
      |      ^

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