Submission #1107802

#TimeUsernameProblemLanguageResultExecution timeMemory
1107802stdfloatChessboard (IZhO18_chessboard)C++17
70 / 100
874 ms2120 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define pb push_back #define ff first #define ss second #define pii pair<int, int> int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; pii p1[k], p2[k]; for (int i = 0; i < k; i++) { cin >> p1[i].ff >> p1[i].ss >> p2[i].ff >> p2[i].ss; p1[i].ff--; p1[i].ss--; p2[i].ff--; p2[i].ss--; } ll ans = LLONG_MAX; for (int ii = 1; ii * ii <= n; ii++) { if (n % ii) continue; for (auto i : {ii, n / ii}) { if (i == n) continue; int x = n / i; ll cnt1 = ((ll)((x + 1) >> 1) * ((x + 1) >> 1) + (ll)(x >> 1) * (x >> 1)) * i * i; ll cnt2 = ((ll)((x + 1) >> 1) * (x >> 1) + (ll)(x >> 1) * ((x + 1) >> 1)) * i * i; for (int j = 0; j < k; j++) { pii x = p1[j], y = p2[j]; vector<pair<pii, pii>> v; if (x.ss / i != y.ss / i) { if (x.ss % i) { v.pb({x, {y.ff, x.ss + i - x.ss % i - 1}}); x.ss += i - x.ss % i; } if ((y.ss + 1) % i) { v.pb({{x.ff, y.ss - y.ss % i}, y}); y.ss -= y.ss % i + 1; } } v.pb({x, y}); vector<pair<pii, pii>> u1, u2; for (auto [x, y] : v) { if (x.ff / i == y.ff / i) { if (x.ss / i == y.ss / i) u1.pb({x, y}); else u2.pb({x, y}); } else { if (x.ff % i) { u1.pb({x, {x.ff + i - x.ff % i - 1, y.ss}}); x.ff += i - x.ff % i; } if ((y.ff + 1) % i) { u1.pb({{y.ff - y.ff % i, x.ss}, y}); y.ff -= y.ff % i + 1; } u2.pb({x, y}); } } for (auto [x, y] : u1) { if (((x.ff / i) & 1) == ((x.ss / i) & 1)) { cnt1 -= (ll)(y.ff - x.ff + 1) * (y.ss - x.ss + 1); cnt2 += (ll)(y.ff - x.ff + 1) * (y.ss - x.ss + 1); } else { cnt1 += (ll)(y.ff - x.ff + 1) * (y.ss - x.ss + 1); cnt2 -= (ll)(y.ff - x.ff + 1) * (y.ss - x.ss + 1); } } for (auto [x, y] : u2) { bool tr = (((x.ff / i) & 1) == ((x.ss / i) & 1)); int r = (y.ff - x.ff + 1) / i, c = (y.ss - x.ss + 1) / i; cnt1 -= (ll)((r & 1) && (c & 1) ? (tr ? 1 : -1) : 0) * (i - x.ff % i) * (y.ss + 1); cnt2 -= (ll)((r & 1) && (c & 1) ? (tr ? -1 : 1) : 0) * (i - x.ff % i) * (y.ss + 1); } } ans = min({ans, cnt1, cnt2}); } } cout << ans; }
#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...