Submission #1131212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131212		why1	Chessboard (IZhO18_chessboard)	C++20	39 / 100	2094 ms	3912 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};

ll n,k;
vector<ll> v[N+1];
int cunt=0;

ll calc(bool state,ll d){
	ll res=0,ok=state;
	for(int x = 1; x <= n; x++){
		ll cur=d,ok2=ok,i=0;
		while(i<v[x].sz){
			ll j=i,cnt=0;
			while(j<v[x].sz && v[x][j]<=cur){
				cnt++;
				j++;
				cunt++;
			}
			if(ok2) res+=d-cnt;
			else res+=cnt;
			ok2^=1;
			cur+=d;
			i=j;
		}
		if(cur<=n){
			cur-=d;
			ll p=(n-cur)/d;
			if(ok2)
				p=(p+1)/2;
			else
				p/=2;
			p*=d;
			res+=p;
		}
		if(x%d==0){
			ok^=1;
		}
	}
	assert(cunt<=k);
	cunt=0;
	return res;
}

void solve() {
	cin>>n>>k;
	for(int i = 1; i <= k; i++){
		ll x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		v[x1].pb(y1);
	}
	for(int i = 1; i <= n; i++){
		sort(all(v[i]));
	}
	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(0,d));
		ans=min(ans,calc(1,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: 0 / 8
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 0 / 23
• Subtask 6: 0 / 30