Submission #168983

#	Time	Username	Problem	Language	Result	Execution time	Memory
168983		cormac	Chessboard (IZhO18_chessboard)	C++14	100 / 100	443 ms	4416 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 find(ll p, ll k) {
    return p / (2 * k) * k + min(k, p % (2 * k));
}

ll count1d(ll x, ll w, ll k) {
    return find(x + w, k) - find(x, k);
}

ll count2d(ll x, ll y, ll w, ll h, ll k) {
    ll r = count1d(x, w, k); 
    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, tA;
    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; tA += w * h;
        blocks[i] = make_tuple(w*h, y, x, h, w);
    }

    ll best = INF;

    ROF(i, 1, N) {
        if (N % i != 0) continue;

        ll cA = tA;
        
        ll c1 = count2d(0, 0, N, N, i);
        ll c2 = A - c1;

        for (bk block : blocks) {
            ll x, y, w, h, a;
            tie(a, x, y, w, h) = block;    
            ll overlap = count2d(x, y, w, h, i);
            cA -= a;
            c1 -= overlap;
            c1 += a - overlap;
            c2 += overlap;
            c2 -= a - overlap;
            if (c2 - cA >= best && c1 - cA >= best) break;
        }
        best = min(best, c1);
        best = min(best, c2);
    }
    
    cout << best << endl;
}

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:59:16: warning: 'tA' may be used uninitialized in this function [-Wmaybe-uninitialized]
             cA -= a;
             ~~~^~~~

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