Submission #290549

#	Time	Username	Problem	Language	Result	Execution time	Memory
290549		nandonathaniel	Chessboard (IZhO18_chessboard)	C++14	100 / 100	363 ms	6008 KiB

chessboard

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MAXN=100005;

LL n,k,ans,xl[MAXN],xr[MAXN],yl[MAXN],yr[MAXN];

LL prefix(LL x,LL d){
	//consider ujung kiri atas hitam
	//di chessboard yang ukuran perwarnanya d*d
	//count hitam di prefix dari x 
	return (x/(2*d))*d+min(x%(2*d),d);
}

void calc(LL d){
	if(d==n)return;
	LL hitam=0,putih=0,genap=((n/d)*(n/d)+1)/2,ganjil=((n/d)*(n/d))/2;
	putih=ganjil*d*d;  //consider ujung kiri atas putih
	hitam=genap*d*d;   //consider ujung kiri atas hitam
	for(LL i=1;i<=k;i++){
		LL blackrow=prefix(xr[i],d)-prefix(xl[i]-1,d),whiterow=xr[i]-xl[i]+1-blackrow;
		LL blackcolumn=prefix(yr[i],d)-prefix(yl[i]-1,d),whitecolumn=yr[i]-yl[i]+1-blackcolumn;
		//anggep consider ujung kiri atas hitam kaya di gambar,count black in this subrectangle
		LL black=blackrow*blackcolumn+whiterow*whitecolumn;
		LL white=(xr[i]-xl[i]+1)*(yr[i]-yl[i]+1)-black;
		hitam-=black;
		putih+=black;
		hitam+=white;
		putih-=white;
	}
	ans=min(ans,min(hitam,putih));
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin >> n >> k;
	for(LL i=1;i<=k;i++){
		cin >> xl[i] >> yl[i] >> xr[i] >> yr[i];
	}
	ans=n*n;
	for(LL i=1;i*i<=n;i++){
		if(n%i!=0)continue;
		calc(i);calc(n/i);
	}
	cout << ans << '\n';
	return 0;
}

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