Submission #1124143

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124143		boris_7	Chessboard (IZhO18_chessboard)	C++20	47 / 100	289 ms	327680 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);
        }
    }
    if(div.size()==1){
        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 cnt1=n*n/2;
        for(ll i = 0;i<n;i++){
            for(auto j:v[i]){
                if(!j.second) continue;
                if((i+j.first)%2) cnt1--;
                else cnt1++;
            }
        }
        ll cnt2=n*n/2+(n%2);
        for(ll i = 0;i<n;i++){
            for(auto j:v[i]){
                if(!j.second) continue;
                if((i+j.first)%2) cnt2++;
                else cnt2--;
            }
        }
        cout<<min(cnt1,cnt2)<<endl;
        return;
    }
    vector<vector<ll>>v(n,vector<ll>(n));
    for(ll i = 0;i<k;i++){
        ll x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        --x1;
        --y1;
        --x2;
        --y2;
        v[x1][y1]=1-v[x1][y1];
    }
    ll ans = 1e6;
    for(ll &d:div){
        ll cnt = 0,cnt1=0;
        for(ll i = 0;i<n;i++){
            for(ll j = 0;j<n;j++){
                ll x = ((i/d)%2)^((j/d)%2);
                if(v[i][j]==x) cnt++;
                else cnt1++;
            }
        }
        ans = min(ans,cnt);
        ans = min(ans,cnt1);
    }
    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: 0 / 23
• Subtask 6: 0 / 30