Submission #168590

#	Time	Username	Problem	Language	Result	Execution time	Memory
168590		cormac	Chessboard (IZhO18_chessboard)	C++14	100 / 100	1274 ms	5248 KiB

chessboard

#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)

using ll = long long;
using bk = tuple<ll, ll, ll, ll, ll>;

ll INF = 1LL << 60;

ll count1d(ll x, ll w, ll k) {
    ll sx = k * ((x / k) + (x % k != 0));
    ll ex = (x + w) / k * k;
    if (ex < sx) return w;
    ll m = (ex - sx);
    return (sx - x) + (x + w - ex) * ((sx ==x) != (m/k%2==1)) + (m / k / 2) * k + k * ((m/k)%2 && (sx == x));
}

ll count2d(ll x, ll y, ll w, ll h, ll k) {
    ll r = count1d(x, w, k); 
    if ((x / k + y / k) % 2 == 1) r = w - r;
    ll c = count1d(y, h, k);
    return  r * c + (w-r) * (h-c);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    ll N, K, A;
    cin >> N >> K;
    A = N*N;
    
    vector<bk> blocks (K);
    F0R(i, K) {
        ll x, y, w, h;
        cin >> x >> y >> w >> h;
        w-=x; h-=y;
        --x; --y; ++w; ++h;
        blocks[i] = make_tuple(y, x, h, w, w*h);
    }

    ll best = INF;
    for (ll t = 1; t * t <= N; ++t) {
        if (N % t != 0) continue;
        for (ll i : {t, N / t}) {
            if (i == N) continue;
            ll c1 = count2d(0, 0, N, N, i);
            ll c2 = A - c1;
            for (bk block : blocks) {
                ll x, y, w, h, a;
                tie(x, y, w, h, a) = block;    
                ll overlap = count2d(x, y, w, h, i);
                c1 -= overlap;
                c1 += a - overlap;
                c2 -= a - overlap;
                c2 += overlap;
            }
            best = min(best, c1);
            best = min(best, c2);
        }
    }
    cout << best << endl; 
}

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