Submission #1131224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131224		why1	Chessboard (IZhO18_chessboard)	C++20	70 / 100	386 ms	1512 KiB

chessboard

#include <bits/stdc++.h>
using namespace std;

#define ll unsigned long long
#define pb push_back
#define pii pair<int,int>
#define sz size()
#define all(v) v.begin(),v.end()
#define fi first
#define se second

const int N = 1e5;
const int mod = 1e9+7;
const ll INF = 1e18;

const int di[]={1,-1,0,0};
const int dj[]={0,0,1,-1};

int n,k;
vector<pii> v;

ll calc(int ok,ll d){
	ll res=((n/d)*(n/d)+ok)/2;
	res*=d*d;
	for(auto [X,Y]: v){
		int x=(X+d-1)/d;
		int y=(Y+d-1)/d;
		if(ok){
			if(x%2==y%2)
				res--;
			else
				res++;
		}
		else{
			if(x%2!=y%2)
				res--;
			else
				res++;
		}
	}
	return res;
}

void solve() {
	cin>>n>>k;
	for(int i = 1; i <= k; i++){
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		v.pb({x1,y1});
	}
	vector<ll> D;
	for(ll i = 1; i*i <= n; i++){
		if(n%i==0){
			D.pb(i);
			if(i*i!=n && i!=1)
				D.pb(n/i);
		}
	}
	ll ans=INF;
	for(auto d: D){
	//	cout<<d<<" "<<calc(0,d)<<" "<<calc(1,d)<<"\n";
		ans=min(ans,calc(1,d));
		ans=min(ans,calc(0,d));
	}
	cout<<ans<<"\n";
}

int main() {

	//freopen("cowrun.in","r",stdin);
	//freopen("cowrun.out","w",stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t=1;
	//cin>>t;
	while(t--) {
        solve();
	}

    return 0;
}

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