Submission #1201124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201124		Gray	Chessboard (IZhO18_chessboard)	C++20	100 / 100	788 ms	3400 KiB

chessboard

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair

const ll INF = 2e18;
const ll MOD = 1e9+7;

vector<pair<pair<ll, ll>, pair<ll, ll>>> a;
ll f(ll i, ll j, ll k){
    ll ii = i-i%k, ij=j-j%k; ll iblock = ii/k, jblock = ij/k;
    ll cnt = iblock/2*ij*k + iblock%2*k*k*(jblock/2+jblock%2)+((i-ii)*(jblock/2+(iblock%2==0 and jblock%2))+(j-ij)*(iblock/2+(jblock%2==0 and iblock%2)))*k+(1-((i/k+(i%k?1:0))+(j/k+(j%k?1:0)))%2)*(i-ii)*(j-ij);
    return cnt;
}
ll calc(ll k, ll n){
    ll res = f(n, n, k);
    // cout << n << "-" << k << " " << res << ln;
    ll bwc=0;
    for (auto &ch:a){
        ll contr = 2*(f(ch.ss.ff, ch.ss.ss, k)-f(ch.ff.ff-1, ch.ss.ss, k)-f(ch.ss.ff, ch.ff.ss-1, k)+f(ch.ff.ff-1, ch.ff.ss-1, k))-(ch.ss.ss-ch.ff.ss+1)*(ch.ss.ff-ch.ff.ff+1);
        bwc += contr;
    }
    return min(res-bwc, n*n-res+bwc);
}

void solve(){
    ll n, m; cin >> n >> m;
    a.resize(m);
    for (ll i=0; i<m; i++){
        cin >> a[i].ff.ff >> a[i].ff.ss >> a[i].ss.ff >> a[i].ss.ss;
    }
    ll res=INF;
    for (ll i=1; i*i<=n; i++){
        if (n%i==0){
            res=min(res, calc(i, n));
            if (n/i!=n) res=min(res, calc(n/i, n));
        }
    }
    cout << res << ln;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    auto start = chrono::high_resolution_clock::now();
    ll t=1;
    // cin >> t;
    while (t--) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

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