제출 #1180810

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1180810		PieArmy	Chessboard (IZhO18_chessboard)	C++20	100 / 100	342 ms	3568 KiB

chessboard

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
using namespace std;
#define int ll
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=(k-(a%k))+(b%k)+1-k;
	}
	else{
		res=(k-(a%k))-(b%k)-1;
	}
	if(((a/k)&1)==((h/k)&1))res=-res;
	return res;
}

int32_t 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: 30 / 30