Submission #168435

#	Time	Username	Problem	Language	Result	Execution time	Memory
168435		mosiashvililuka	Chessboard (IZhO18_chessboard)	C++14	39 / 100	93 ms	11512 KiB

chessboard

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,mas[1009][1009],jj,jjj,pas,zx,xc,zzx,zxc;
pair <pair <long long, long long>, pair <long long, long long> > p[100009];
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>b;
	pas=a*a;
	for(i=1; i<=b; i++){
		cin>>p[i].first.first>>p[i].first.second>>p[i].second.first>>p[i].second.second;
		if(a<=1000){
			mas[p[i].first.first][p[i].first.second]++;
		}else{
			if((p[i].first.first+p[i].first.second)%2==0) zx++; else xc++;
		}
	}
	zzx=a/2*a/2;
	zxc=(a/2+1)*(a/2+1);
	if(a>1000){
		d=xc+zxc-zx;
		e=zx+zzx-xc;
		cout<<min(d,e);
		return 0;
	}
	for(i=1; i<=1002; i++){
		for(j=1; j<=1002; j++) mas[i][j]+=mas[i-1][j]+mas[i][j-1]-mas[i-1][j-1];
	}
	for(c=1; c<a; c++){
		if(a%c!=0) continue;
		long long ans=0;
		e=c*c;
		for(i=c; i<=a; i+=c){
			for(j=c; j<=a; j+=c){
				d=mas[i][j]-mas[i-c][j]-mas[i][j-c]+mas[i-c][j-c];
				if((i/c+j/c)%2==0) ans+=d; else ans+=e-d;
			}
		}
/*		if(ans==11){
			cout<<c<<" 1"<<endl;
		}*/
		if(pas>ans) pas=ans;
		ans=0;
		for(i=c; i<=a; i+=c){
			for(j=c; j<=a; j+=c){
				d=mas[i][j]-mas[i-c][j]-mas[i][j-c]+mas[i-c][j-c];
				if((i/c+j/c)%2==1) ans+=d; else ans+=e-d;
			}
		}
/*		if(ans==11){
			cout<<c<<" 2"<<endl;
		}*/
		if(pas>ans) pas=ans;
	}
	cout<<pas;
	return 0;
}

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