Submission #492395

#TimeUsernameProblemLanguageResultExecution timeMemory
492395hohohahaChessboard (IZhO18_chessboard)C++14
100 / 100
1130 ms2800 KiB
#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){
      |               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...