Submission #715012

#TimeUsernameProblemLanguageResultExecution timeMemory
715012StickfishChessboard (IZhO18_chessboard)C++17
100 / 100
936 ms5828 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; using ll = long long; bool get_color(pair<ll, ll> p, ll d) { return (p.first / d + p.second / d) & 1; } ll intersect(pair<pair<ll, ll>, pair<ll, ll>> r1, pair<pair<ll, ll>, pair<ll, ll>> r2) { ll w = min(r1.second.first, r2.second.first) - max(r1.first.first, r2.first.first); ll h = min(r1.second.second, r2.second.second) - max(r1.first.second, r2.first.second); //cout << w << ' ' << h << endl; if (w < 0 || h < 0) return 0; return w * h; } signed main() { ll n, k; cin >> n >> k; vector<pair<pair<ll, ll>, pair<ll, ll>>> rect(k); for (ll i = 0; i < k; ++i) { cin >> rect[i].first.first >> rect[i].first.second >> rect[i].second.first >> rect[i].second.second; --rect[i].first.first, --rect[i].first.second, --rect[i].second.first, --rect[i].second.second; } vector<ll> divs; for (ll p = 1; p < n; ++p) { if (n % p == 0) divs.push_back(p); } ll szd = divs.size(); vector<ll> ans(szd); for (ll di = 0; di < szd; ++di) { ll d = divs[di]; if (n / d == 0) ans[di] = n * n / 2; else ans[di] = d * d * ((n / d) * (n / d) / 2); } for (auto [ld, ru] : rect) { for (ll di = 0; di < szd; ++di) { ll d = divs[di]; ll r = ld.first + (ru.first - ld.first) % (2 * d); ll u = ld.second + (ru.second - ld.second) % (2 * d); pair<pair<ll, ll>, pair<ll, ll>> rct = {ld, {r + 1, u + 1}}; ll bi = ld.first / (2 * d) * (2 * d); ll bj = ld.second / (2 * d) * (2 * d); for (ll i = 0; i < 4; ++i) for (ll j = 0; j < 4; ++j) { ll val = intersect(rct, {{bi + d * i, bj + d * j}, {bi + d * i + d, bj + d * j + d}}); if ((i + j) % 2) ans[di] -= val; else ans[di] += val; } //ans[di] += intersect(rct, {{bi, bj}, {bi + d, bj + d}}); //ans[di] -= intersect(rct, {{bi + d, bj}, {bi + 2 * d, bj + d}}); //ans[di] -= intersect(rct, {{bi, bj + d}, {bi + d, bj + 2 * d}}); //ans[di] += intersect(rct, {{bi + d, bj + d}, {bi + 2 * d, bj + 2 * d}}); } } ll mnans = n * n; for (auto x : ans) { mnans = min({mnans, x, n * n - x}); } cout << mnans << '\n'; }
#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...