Submission #492395

#	Time	Username	Problem	Language	Result	Execution time	Memory
492395		hohohaha	Chessboard (IZhO18_chessboard)	C++14	100 / 100	1130 ms	2800 KiB

chessboard

#include <bits/stdc++.h>
using namespace std;
 
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define ll long long
 
struct rect{ int x1, y1, x2, y2; };
 
ll n, k, ans = 1e18; vector<rect> A;
 
void solve(ll sz, int T){
    ll bl = (n / sz) * (n / sz) / 2;
    if ((n / sz) % 2) bl += T;
    ll res = sz * sz * bl;
    
    auto eval = [&](int x1, int y1, int x2, int y2, ll area){
        
        int dX = x2 - x1 + 1;
        int dY = y2 - y1 + 1;
        if (!dX or !dY) return 0LL;
        
        ll L = (dY - 1) / sz + 1; //ceil div to take care of smoll square
        ll H = (dX - 1) / sz + 1; 
        ll black = L * H / 2;
 
        //odd x odd dimension will have one extra of white/black
        int a = (x1 / sz) % 2, b = (y1 / sz) % 2;
        if (L % 2 and H % 2) black += (a ^ b ^ T); //T = 1 means start is black
        ll white = L * H - black;
 
        return black * area - white * area; //color operations saved
    };
 
    for (auto [x1, y1, x2, y2] : A){
        
        ll VU = sz - (x1 % sz);
        ll VD = (x2 % sz) + 1;
 
        ll HL = sz - (y1 % sz);
        ll HR = (y2 % sz) + 1;
 
        //small dimension cases
        if (VU + VD > x2 - x1 + 1) VU = x2 - x1 + 1, VD = 0;
        if (HL + HR > y2 - y1 + 1) HL = y2 - y1 + 1, HR = 0;
        
        //inner rect
        res -= eval(x1 + VU, y1 + HL, x2 - VD, y2 - HR, (ll)sz * sz); 
 
        //corner rec
        res -= eval(x1, y1, x1 + VU - 1, y1 + HL - 1, HL * VU); //top left
        res -= eval(x2 - VD + 1, y1, x2, y1 + HL - 1, VD * HL); //bottom left
        res -= eval(x1, y2 - HR + 1, x1 + VU - 1, y2, HR * VU); //top right
        res -= eval(x2 - VD + 1, y2 - HR + 1, x2, y2, VD * HR); //bottom right
 
        //side rec
        res -= eval(x1 + VU, y1, x2 - VD, y1 + HL - 1, sz * HL); //left
        res -= eval(x1, y1 + HL, x1 + VU - 1, y2 - HR, sz * VU); //up
        res -= eval(x1 + VU, y2 - HR + 1, x2 - VD, y2, sz * HR); //right
        res -= eval(x2 - VD + 1, y1 + HL, x2, y2 - HR, sz * VD); //down
    }
    ans = min(ans, res);
}
 
int main(){
    cin >> n >> k; A.resize(k);
    for (auto &i : A){
        cin >> i.x1 >> i.y1 >> i.x2 >> i.y2;
        i.x1--; i.y1--; i.x2--; i.y2--; //0 indexed makes mod ops easier
    }
    FOR(i, 2, n + 1) if (!(n % i)) solve(n / i, 0), solve(n / i, 1);
    cout<<ans<<endl;
}

Compilation message (stderr)

chessboard.cpp: In function 'void solve(long long int, int)':
chessboard.cpp:34:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |     for (auto [x1, y1, x2, y2] : 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