Submission #333311

#	Time	Username	Problem	Language	Result	Execution time	Memory
333311		Bill_00	Chessboard (IZhO18_chessboard)	C++14	100 / 100	1536 ms	5996 KiB

chessboard

#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 100000000000000000
typedef long long ll;
using namespace std;
struct point{
	ll x1,y1,x2,y2;
};
point p[100001];
ll n,k;
ll solve(ll x,ll y,ll sz){
	if(x==n+1 || y==n+1) return (ll)0;
	ll black=0;
	ll xx=((x+sz-1)/sz)*sz;
	ll yy=((y+sz-1)/sz)*sz;
	// cout << xx << ' ' << yy << '\n';
	ll a=(n-xx)/sz;
	ll b=(n-yy)/sz;
	black+=(((a*b+1)/2)*sz*sz);
	ll c=xx-x+1;
	ll d=yy-y+1;
	ll aa,bb;
	if(a%2) bb=b/2;
	else bb=(b+1)/2;
	if(b%2) aa=a/2;
	else aa=(a+1)/2;
	black+=(bb*c*sz);
	black+=(aa*d*sz);
	if((xx/sz+yy/sz)%2==0) black+=(c*d);
	return black;
}
int main(){
	//ios_base::sync_with_stdio(NULL);
	// cin.tie(NULL);
	// cout.tie(NULL);
	cin >> n >> k;

	for(ll i=1;i<=k;i++){
		cin >> p[i].x1 >> p[i].y1 >> p[i].x2 >> p[i].y2;
	}
	ll ans=INF;
	// cout << solve(4,1,) << '\n';
	for(ll i=1;i<n;i++){
		if(n%i==0){
			ll black=0,white=0;
			for(ll j=1;j<=k;j++){
				ll z=(solve(p[j].x1,p[j].y1,i)-solve(p[j].x1,p[j].y2+1,i)-solve(p[j].x2+1,p[j].y1,i)+solve(p[j].x2+1,p[j].y2+1,i));
				black+=(z);
				white+=((p[j].x2+1-p[j].x1)*(p[j].y2+1-p[j].y1)-z);
				// if(i==2) cout << white << '\n';
			}
			// cout << black << ' ' << white << '\n';
			if((n/i)%2){
				ans=min(ans,((n*n+i*i)/2-black+white));
				ans=min(ans,((n*n-i*i)/2-white+black));
			}
			else ans=min(ans,n*n/2-abs(black-white));
		}
	}
	cout << ans;
}

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