Submission #1124198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124198		boris_7	Chessboard (IZhO18_chessboard)	C++20	70 / 100	1233 ms	11004 KiB

chessboard

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
    ll n,k;
    cin>>n>>k;
    vector<ll>div;
    for(ll i = 1;i*i<=n;i++){
        if(n%i==0){
            div.push_back(i);
            if(i==1) continue;
            div.push_back(n/i);
        }
    }
    vector<map<ll,ll>>v(n);
    for(ll i = 0;i<k;i++){
        ll x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        --x1;
        --y1;
        v[x1][y1]=1-v[x1][y1];
    }
    ll ans = 1e12;
    for(ll &d:div){
        ll a = 0,b=0;
        if((n/d)%2==0) a = b = (n*n)/2;
        else {
            a = (n/d/2+1)*(n/d/2+1)+(n/d/2)*(n/d/2);
            b = (n*n/d/d)-a;
            a *= d*d;
            b *= d*d;
        }
        ll c1=0,c2=0;
        for(ll i = 0;i < n;i++){
            for(auto &j:v[i]){
                if(!j.second) continue;
                ll x = (i/d+j.first/d)%2;
                if(x==0) c1++;
                else c2++;
            }
        }
        ans = min(ans,min(a-c1+c2,b-c2+c1));
    }
    cout<<ans<<endl;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    // ll t;cin>>t;while(t--)
        solve();
}

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