Submission #1180782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180782		PieArmy	Chessboard (IZhO18_chessboard)	C++20	70 / 100	266 ms	2204 KiB

chessboard

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
using namespace std;

ll n,m;
ll ans=0;
pair<pair<int,int>,pair<int,int>>arr[100023];

ll cal(int k,int a,int b,int h){
	int res=0;
	if(b/k==a/k){
		res=b-a+1;
	}
	else if(((a/k)&1)==((b/k)&1)){
		res=(b-(b%k)-(a+k-(a%k))-k)/(k*2)+(k-(a%k))+(b%k)+1;
	}
	else{
		res=(b-(b%k)-(a+k-(a%k)))/(k*2)+(k-(a%k));
	}
	if(((a/k)&1)==((h/k)&1))res=b-a+1-res;
	return res-(b-a+1-res);
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n>>m;
	ans=n*n;
	for(int i=1;i<=m;i++){
		cin>>arr[i].fr.fr>>arr[i].fr.sc>>arr[i].sc.fr>>arr[i].sc.sc;
		arr[i].fr.fr--;
		arr[i].fr.sc--;
		arr[i].sc.fr--;
		arr[i].sc.sc--;
	}
	for(int i=1;i*i<=n;i++){
		if(i*(n/i)==n){
			ll sum=0;
			for(int j=1;j<=m;j++){
				sum+=cal(i,arr[j].fr.fr,arr[j].sc.fr,arr[j].fr.sc)*(((((arr[j].fr.fr/i)&1)==((arr[j].fr.sc/i)&1))?1:-1)*cal(i,arr[j].fr.sc,arr[j].sc.sc,arr[j].fr.fr));
			}
			ans=min(ans,min((((n/i)&1)?(n*n-i*i)/2:(n*n)/2)+sum,(((n/i)&1)?(n*n+i*i)/2:(n*n)/2)-sum));
			if(i==1)continue;
			i=n/i;
			sum=0;
			for(int j=1;j<=m;j++){
				sum+=cal(i,arr[j].fr.fr,arr[j].sc.fr,arr[j].fr.sc)*(((((arr[j].fr.fr/i)&1)==((arr[j].fr.sc/i)&1))?1:-1)*cal(i,arr[j].fr.sc,arr[j].sc.sc,arr[j].fr.fr));
			}
			ans=min(ans,min((((n/i)&1)?(n*n-i*i)/2:(n*n)/2)+sum,(((n/i)&1)?(n*n+i*i)/2:(n*n)/2)-sum));
			i=n/i;
		}
	}
	cout<<ans;
}

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