Submission #378910

#	Time	Username	Problem	Language	Result	Execution time	Memory
378910		Fireball0424	Chessboard (IZhO18_chessboard)	C++14	16 / 100	39 ms	5228 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] = {};
		sum[0] = ((x / len) * (y / len) / 2) * (len * len); // all
		int ty = y % len, tx = x % len;
		if((x / len) & 1){
			sum[1] = ty * (x / len) / 2 * len;
		}
		else{
			sum[1] = ty * (x / len + 1) / 2 * len;
		}
		if((y / len) & 1){
			sum[2] = tx * (x / len) / 2 * len;
		}
		else{
			sum[2] = ty * (x / len + 1) / 2 * len;
		}
		if(((x / len) & 1) != ((y / len) & 1)){
			sum[3] = ty * tx;
		}
		int res = 0;
		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) continue;
		int sum[4] = {};
		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];
		sum[3] = n * n - (sum[1] + sum[2]);
		mn = min(mn, sum[1] + sum[2]);
		mn = min(mn, sum[3]);
	}
	cout << mn;
}

main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
}

Compilation message (stderr)

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

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