Submission #1002364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002364		Tob	Chessboard (IZhO18_chessboard)	C++14	70 / 100	197 ms	4388 KiB

chessboard

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

const int N = 1e5 + 7;

ll n, m;
pair <pii, pii> re[N];

int main () {
	FIO;
	cin >> n >> m;
	
	for (int i = 0; i < m; i++) {
		int x, y, x2, y2; cin >> x >> y >> x2 >> y2; x--; y--; x2--; y2--;
		re[i] = {{x, y}, {x2, y2}};
	}
	
	ll mn = 1e18;
	for (ll i = 1; i < n; i++) {
		if (n % i) continue;
		ll cnt[2] = {0};
		for (int j = 0; j < m; j++) {
			ll a = re[j].F.F, b = re[j].F.S, c = re[j].S.F, d = re[j].S.S;
			ll aa = a/i*i+i, bb = b/i*i+i, cc = c/i*i-1, dd = d/i*i-1;
			ll ro = (cc-aa+1)/i, co = (dd-bb+1)/i;
			int o = (aa/i+bb/i)%2;
			if (ro < 0 && co < 0) {
				cnt[o] += (c-a+1)*(d-b+1);
				continue;
			}
			if (ro < 0) {
				ro = c-a+1;
				cnt[o] += ro*(bb-b);
				cnt[(o+co+1)&1] += ro*(d-dd);
				cnt[0] += ro*(co/2+(co&1&&o==1));
				cnt[1] += ro*(co/2+(co&1&&o==0));
				continue;
			}
			if (co < 0) {
				co = d-b+1;
				cnt[o] += co*(aa-a);
				cnt[(o+ro+1)&1] += co*(c-cc);
				cnt[0] += co*(ro/2+(ro&1&&o==1));
				cnt[1] += co*(ro/2+(ro&1&&o==0));
				continue;
			}
			cnt[0] += ro*co/2; cnt[1] += ro*co/2;
			if (ro*co&1) cnt[o]++;
			
			cnt[0] += (ro/2+(o^1&&ro&1))*(min(bb,d+1)-b) + (ro/2+((o+co)%2==0&&ro&1))*(d-max(b-1,dd));
			cnt[1] += (ro/2+(o^1&&ro&1))*(min(bb,d+1)-b) + (ro/2+((o+co)%2==1&&ro&1))*(d-max(b-1,dd));
			
			cnt[0] += (co/2+(o^1&&co&1))*(min(aa,c+1)-a) + (co/2+((o+ro)%2==0&&co&1))*(c-max(a-1,cc));
			cnt[1] += (co/2+(o^1&&co&1))*(min(aa,c+1)-a) + (co/2+((o+ro)%2==1&&co&1))*(c-max(a-1,cc));
			
			cnt[o] += (min(aa,c+1)-a)*(min(bb,d+1)-b);
			cnt[(o+ro-1)&1] += (min(aa,c+1)-a)*(d-max(b-1,dd));
			cnt[(o+co-1)&1] += (c-max(a-1,cc))*(min(bb,d+1)-b);
			cnt[(o+ro+co)&1] += (c-max(a-1,cc))*(d-max(b-1,dd));
		}
		ll dod = (n/i&1)*i*i;
		ll cost = min((n*n-dod)/2+dod - cnt[0] + cnt[1], (n*n-dod)/2 - cnt[1] + cnt[0]);
		mn = min(mn, cost);
	}
	cout << mn;

	return 0;
}

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