Submission #155123

#TimeUsernameProblemLanguageResultExecution timeMemory
155123Dasha_GnedkoChessboard (IZhO18_chessboard)C++14
8 / 100
35 ms2296 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/detail/standard_policies.hpp> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> //#pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4") #define ll long long #define ld long double #define pb push_back #define F first #define S second #define endl '\n' #define int long long using namespace std; //using namespace __gnu_pbds; //template <typename T> using ordered_set = tree <T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update>; const int N = 1e6 + 100; const int M = 21890; const ll mod = 1e9 + 7; const ll MOD = 998244353; const int P = 1336; const ld eps = 0.000000001; const int inf = 1e9 + 7; mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count()); int l1[N], r1[N], l2[N], r2[N]; int m; pair <int, pair <int, int> > get(int r, int x, int y, int fl) { int x1 = x / r; if (x % r) x1++; int y1 = y / r; if (y % r) y1++; int f = y1 % 2; if (x1 % 2 == 0) { f = !f; } int kx = x / r; if (x % r) kx++; int nx = kx * r - x + 1; int ky = y / r; if (y % r) ky++; int ny = ky * r - y + 1; if (fl) return {!f, {nx, ny}}; } int solve(int r, int x1, int y1, int x2, int y2, bool fl) { if (x1 > x2 || y1 > y2) return 0; int vs = 0; int bx1 = x1 / r, bx2 = x2 / r; if (x1 % r < 2) bx1++; else bx1 += 2; int by1 = y1 / r, by2 = y2 / r; if (y1 % r < 2) by1++; else by1 += 2; if (r == 1) { bx1 = x1; by1 = y1; bx2 = x2; by2 = y2; } // cout << "! " << bx1 << " " << bx2 << " " << by1 << " " << by2 << endl; if (bx1 > bx2 || by1 > by2) { if (bx1 > bx2 && by1 > by2) { int vs = 0; pair < int, pair < int, int > > p = get(r, x1, y1, fl); // cout << p.F << " " << p.S.F << " " << p.S.S << endl; p.S.F = min(p.S.F, x2 - x1 + 1); p.S.S = min(p.S.S, y2 - y1 + 1); if (p.F != fl) vs += p.S.F * p.S.S; pair < int, pair < int, int > > p1 = get(r, x1, y1 + p.S.S + 1, fl); p1.S.F = min(p1.S.F, max(0ll, x2 - x1 + 1)); p1.S.S = min(p1.S.S, max(0ll, y2 - (y1 + p.S.S) + 1)); // cout << p1.F << " " << p1.S.F << " " << p1.S.S << endl; if (p1.F != fl) vs += p1.S.F * p1.S.S; p1 = get(r, x1 + p.S.F + 1, y1, fl); p1.S.F = min(p1.S.F, max(0ll, x2 - (x1 + p.S.F) + 1)); p1.S.S = min(p1.S.S, max(0ll, y2 - y1 + 1)); // cout << p1.F << " " << p1.S.F << " " << p1.S.S << endl; if (p1.F != fl) vs += p1.S.F * p1.S.S; p1 = get(r, x1 + p.S.F + 1, y1 + p.S.S + 1, fl); p1.S.F = min(p1.S.F, max(0ll, x2 - (x1 + p.S.F) + 1)); p1.S.S = min(p1.S.S, max(0ll, y2 - (y1 + p.S.S) + 1)); // cout << p1.F << " " << p1.S.F << " " << p1.S.S << endl; if (p1.F != fl) vs += p1.S.F * p1.S.S; return vs; } if (bx1 > bx2) { int sty = (by1 - 1) * r + 1; // cout << sty << endl; pair < int, pair < int, int > > p = get(r, x1, sty, fl); int vs = 0, ch = 0; p.S.F = min(p.S.F, x2 - x1 + 1); p.S.S = min(p.S.S, y2 - y1 + 1); vs = p.S.F * p.S.S; ch = (x2 - x1 + 1) * r - p.S.F * p.S.S; int k = (by2 - by1 + 1 + 1) / 2; int S1 = vs * k + ch * (by2 - by1 + 1 - k); int S2 = ch * k + vs * (by2 - by1 + 1 - k); // cout << S1 << " " << S2 << endl; int add = solve(r, x1, y1, x2, sty - 1, fl); int ey = by2 * r; add += solve(r, x1, ey + 1, x2, y2, fl); if (p.F == fl) return S2 + add; else return S1 + add; } if (by1 > by2) { int stx = (bx1 - 1) * r + 1; cout << stx << endl; pair < int, pair < int, int > > p = get(r, stx, y1, fl); int vs = 0, ch = 0; p.S.F = min(p.S.F, x2 - x1 + 1); p.S.S = min(p.S.S, y2 - y1 + 1); vs = p.S.F * p.S.S; ch = (y2 - y1 + 1) * r - p.S.F * p.S.S; int k = (bx2 - bx1 + 1 + 1) / 2; int S1 = vs * k + ch * (bx2 - bx1 + 1 - k); int S2 = ch * k + vs * (bx2 - bx1 + 1 - k); // cout << S1 << " " << S2 << endl; int add = solve(r, x1, y1, stx - 1, y2, fl); int ex = bx2 * r; add += solve(r, ex + 1,y1, x2, y2, fl); if (p.F == fl) return S2 + add; else return S1 + add; } return 0; } int x = (bx2 - bx1 + 1 + 1) / 2; int y = (by2 - by1 + 1 + 1) / 2; int addx = bx2 - bx1 + 1 - x; int addy = by2 - by1 + 1 - y; int s = x * y + addx * addy; // cout << "! " << s << endl; bool f = 0; if (fl == 0) { if (bx1 % 2) { if (by1 % 2 == 0) f = 1; } else if (by1 % 2) f = 1; } else { if (bx1 % 2) { if (by1 % 2) f = 1; } else if (by1 % 2 == 0) f = 1; } if (f == 0) vs += s * r * r; else vs += ((bx2 - bx1 + 1) * (by2 - by1 + 1) * r * r - s * r * r); int stx = (bx1 - 1) * r + 1; int ex = bx2 * r; int sty = (by1 - 1) * r + 1; int ey = by2 * r; int add = solve(r, x1, y1, stx - 1, y2, fl) + solve(r, ex + 1, y1, x2, y2, fl) + solve(r, stx, y1, ex, sty - 1, fl) + solve(r, stx, ey + 1, ex, y2, fl); // if (vs != 0) cout << f << " " << x1 << " " << y1 << " " << x2 << " " << y2 << endl; return vs + add; } int get_ans(int d, int n) { int S = n * n; n /= d; int kol = (n + 1) / 2; kol *= kol; int c = n / 2; c *= c; int w = kol * d * d + c * d * d; int s1 = 0, s2 = 0; int sum1 = 0, sum2 = 0; for(int i = 0; i < m; i++) { int v1 = solve(d, l1[i], r1[i], l2[i], r2[i], 1), v2 = solve(d, l1[i], r1[i], l2[i], r2[i], 0); sum1 += (l2[i] - l1[i] + 1) * (r2[i] - r1[i] + 1) - v1; sum2 += (l2[i] - l1[i] + 1) * (r2[i] - r1[i] + 1) - v2; s1 += v1; s2 += v2; } // cout << d << " " << s1 << " " << s2 << endl; s1 += w - sum1; s2 += (S - w) - sum2; // cerr << S - w << " " << sum1 << " " << d << " " << s1 << " " << s2 << endl; int ch = min(s1, s2); return ch; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); srand(time(0)); //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); int n; cin >> n >> m; for(int i = 0; i < m; i++) { cin >> l1[i] >> r1[i] >> l2[i] >> r2[i]; // cout << solve(1, l1[i], r1[i], l2[i], r2[i], 1) << endl; } int d = 1; int ans = inf; while (d * d <= n) { if (n % d == 0) { ans = min(ans, get_ans(d, n)); if (d != 1) ans = min(ans, get_ans(n / d, n)); } d++; } cout << ans; }

Compilation message (stderr)

chessboard.cpp: In function 'std::pair<long long int, std::pair<long long int, long long int> > get(long long int, long long int, long long int, long long int)':
chessboard.cpp:58:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
#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...