제출 #1129412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1129412		Tsagana	Chessboard (IZhO18_chessboard)	C++17	0 / 100	20 ms	324 KiB

chessboard

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define aint(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

vector<int> di = {1};
int dif[200005];
int res = 1e12;

int find(int x, int d){
	return x / (2 * d) * d + min(x % (2 * d), d);
}

void solve () {
	int n, k; cin >> n >> k;
	for (int i = 2; i * i <= n; i++) {
		if (n % i != 0) continue ;
		di.pb(i);
		if (i * i != n) di.pb(n / i);
	}
	
	for (int i = 0; i < di.size(); i++) {
		dif[i] = n * n - n * n / (di[i] * di[i]) / 2 * (di[i] * di[i]);
		cout << i << ' ' << di[i] << ' ' << dif[i] << '\n';
	}
	
	int ox, oy, ex, ey;
	while (k--) {
		int x1, x2, y1, y2; cin >> x1 >> y1 >> x2 >> y2; x1--; y1--;
		for (int i = 0; i < di.size(); i++){
			ex = find(x2, di[i]) - find(x1, di[i]);
			ox = x2 - x1 - ex;
			ey = find(y2, di[i]) - find(y1, di[i]);
			oy = y2 - y1 - ey;
			dif[i] += ex * oy + ey * ox - ex * ey - ox * oy;
		}
	}

	for (int i = 0; i < di.size(); i++) res = min(res, min(dif[i], n * n - dif[i]));
	
	cout << res;
}
signed main() {IOS solve(); return 0;}

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