Submission #378545

#	Time	Username	Problem	Language	Result	Execution time	Memory
378545		wiwiho	Chessboard (IZhO18_chessboard)	C++14	8 / 100	42 ms	3180 KiB

chessboard

#include <bits/stdc++.h>

#define mp make_pair
#define F first
#define S second

using namespace std;

typedef long long ll;

using pll = pair<ll, ll>;

ostream& operator<<(ostream& o, pll p){
    return o << '(' << p.F << ',' << p.S << ')';
}

ll iceil(ll a, ll b){
    return (a + b - 1) / b;
}

pll calc(ll l, ll r, ll t){
    ll even = 0, odd = 0;

    if(l / t % 2 == 0) even += iceil(l, t) * t - l;
    else odd += iceil(l, t) * t - l;
    l = iceil(l, t) * t;

    if(l > r) return mp(even, odd);

    if(r / t % 2 == 0) even += r % t + 1;
    else odd += r % t + 1;
    r = r / t * t - 1;

    if(l > r) return mp(even, odd);

    int tmp = (r - l + 1) / t;
    if(l / t % 2 == 0) even += iceil(tmp, 2) * t, odd += tmp / 2 * t;
    else odd += iceil(tmp, 2) * t, even += tmp / 2 * t;

    return mp(even, odd);
}

vector<ll> xl, xr, yl, yr;
int n, k;
ll check(ll t){
    //cerr << "check " << t << "\n";
    ll b = 0, w = 0;
    for(int i = 0; i < k; i++){
        pll px = calc(xl[i], xr[i], t), py = calc(yl[i], yr[i], t);
        //cerr << i << " " << px << " " << py << " " << xl[i] << " " << xr[i] << " " << yl[i] << " " << yr[i] << "\n";
        b += px.F * py.F + px.S * py.S;
        w += px.S * py.F + px.F * py.S;
    }
    pll tp = calc(0, n - 1, t);
    ll tb = tp.F * tp.F + tp.S * tp.S;
    ll tw = tp.S * tp.F + tp.F * tp.S;
    //cerr << "check " << t << " " << b << " " << w << " " << tp << " " << tb << " " << tw << "\n";
    return min(tb - b + w, tw - w + b);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> k;

    xl.resize(k);
    xr.resize(k);
    yl.resize(k);
    yr.resize(k);
    for(int i = 0; i < k; i++){
        cin >> xl[i] >> yl[i] >> xr[i] >> yr[i];
        xl[i]--;
        yl[i]--;
        xr[i]--;
        yr[i]--;
    }

    ll ans = (ll) n * n;
    for(int t = 1; t * t <= n && t < n; t++){
        if(n % t) continue;
        ans = min(ans, check(t));
    }
    cout << ans << "\n";


    return 0;
}

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