# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
40564 | 2018-02-05T01:40:55 Z | Just_Solve_The_Problem | Chessboard (IZhO18_chessboard) | C++11 | 316 ms | 2164 KB |
#include <bits/stdc++.h> using namespace std; #define ll long long #define whatis(x) cout << #x << " is -> " << x << endl; const ll linf = (ll)1e18 + 7; const int N = (int)1e5 + 7; int x1[N], YY[N], x2[N], y2[N]; ll n; int k; ll ans = linf; inline ll gety(ll y,ll len){ if(y <= 0) return 0; ll res = (y / len) / 2 * len; if((y / len) & 1) res += y % len + 1; return res; } inline ll getx(ll x,ll len){ if(x <= 0) return 0; ll res = (x / len) / 2 * len; if((x / len) & 1) res += x % len + 1; return res; } void calc(ll len) { ll odd = 0, even = 0; for(int i = 1,xx,yy; i <= k; i++){ ll o1 = gety(y2[i], len) - gety(YY[i] - 1, len); ll e1 = (y2[i] - YY[i] + 1) - o1; ll o2 = getx(x2[i], len) - getx(x1[i] - 1, len); ll e2 = (x2[i] - x1[i] + 1) - o2; xx = x1[i] / len; yy = YY[i] / len; if(xx & 1) swap(o1,e1); if(yy & 1) swap(o2,e2); ll od = 0, ev = 0; if((xx + yy) & 1){ od = e1 * e2 + o1 * o2; } else{ od = o1 * e2 + e1 * o2; } ev = 1ll * (x2[i] - x1[i] + 1) * (y2[i] - YY[i] + 1) - od; odd += od; even += ev; } ll cnt = 1ll * (n / len) * (n / len); ll res = min(cnt / 2 * len * len + even - odd, (cnt + 1) / 2 * len * len + odd - even); if(res < ans){ ans = res; } } main () { scanf("%lld %d", &n, &k); for (int i = 1; i <= k; i++) { int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d); a--; b--; c--; d--; x1[i] = a; YY[i] = b; x2[i] = c; y2[i] = d; } for (ll i = 1; i * i <= n; i++) { if (n % i == 0) { calc(i); if (i != 1 && n / i != i) calc(n / i); } } printf("%I64d", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 248 KB | Output is correct |
2 | Correct | 1 ms | 352 KB | Output is correct |
3 | Correct | 1 ms | 424 KB | Output is correct |
4 | Correct | 1 ms | 496 KB | Output is correct |
5 | Correct | 1 ms | 568 KB | Output is correct |
6 | Correct | 2 ms | 568 KB | Output is correct |
7 | Correct | 1 ms | 568 KB | Output is correct |
8 | Correct | 1 ms | 584 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 37 ms | 1516 KB | Output is correct |
2 | Correct | 13 ms | 1516 KB | Output is correct |
3 | Incorrect | 25 ms | 1516 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 1516 KB | Output is correct |
2 | Correct | 1 ms | 1516 KB | Output is correct |
3 | Correct | 2 ms | 1516 KB | Output is correct |
4 | Correct | 3 ms | 1516 KB | Output is correct |
5 | Correct | 2 ms | 1516 KB | Output is correct |
6 | Correct | 2 ms | 1516 KB | Output is correct |
7 | Correct | 2 ms | 1516 KB | Output is correct |
8 | Correct | 2 ms | 1516 KB | Output is correct |
9 | Correct | 2 ms | 1516 KB | Output is correct |
10 | Correct | 1 ms | 1516 KB | Output is correct |
11 | Correct | 2 ms | 1516 KB | Output is correct |
12 | Correct | 2 ms | 1516 KB | Output is correct |
13 | Correct | 3 ms | 1516 KB | Output is correct |
14 | Correct | 2 ms | 1516 KB | Output is correct |
15 | Correct | 2 ms | 1516 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 1516 KB | Output is correct |
2 | Correct | 1 ms | 1516 KB | Output is correct |
3 | Correct | 2 ms | 1516 KB | Output is correct |
4 | Correct | 3 ms | 1516 KB | Output is correct |
5 | Correct | 2 ms | 1516 KB | Output is correct |
6 | Correct | 2 ms | 1516 KB | Output is correct |
7 | Correct | 2 ms | 1516 KB | Output is correct |
8 | Correct | 2 ms | 1516 KB | Output is correct |
9 | Correct | 2 ms | 1516 KB | Output is correct |
10 | Correct | 1 ms | 1516 KB | Output is correct |
11 | Correct | 2 ms | 1516 KB | Output is correct |
12 | Correct | 2 ms | 1516 KB | Output is correct |
13 | Correct | 3 ms | 1516 KB | Output is correct |
14 | Correct | 2 ms | 1516 KB | Output is correct |
15 | Correct | 2 ms | 1516 KB | Output is correct |
16 | Correct | 21 ms | 1516 KB | Output is correct |
17 | Correct | 43 ms | 2028 KB | Output is correct |
18 | Correct | 70 ms | 2164 KB | Output is correct |
19 | Correct | 295 ms | 2164 KB | Output is correct |
20 | Correct | 316 ms | 2164 KB | Output is correct |
21 | Correct | 53 ms | 2164 KB | Output is correct |
22 | Correct | 2 ms | 2164 KB | Output is correct |
23 | Correct | 48 ms | 2164 KB | Output is correct |
24 | Correct | 63 ms | 2164 KB | Output is correct |
25 | Correct | 11 ms | 2164 KB | Output is correct |
26 | Correct | 43 ms | 2164 KB | Output is correct |
27 | Correct | 63 ms | 2164 KB | Output is correct |
28 | Correct | 72 ms | 2164 KB | Output is correct |
29 | Correct | 18 ms | 2164 KB | Output is correct |
30 | Correct | 4 ms | 2164 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 37 ms | 1516 KB | Output is correct |
2 | Correct | 13 ms | 1516 KB | Output is correct |
3 | Incorrect | 25 ms | 1516 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 248 KB | Output is correct |
2 | Correct | 1 ms | 352 KB | Output is correct |
3 | Correct | 1 ms | 424 KB | Output is correct |
4 | Correct | 1 ms | 496 KB | Output is correct |
5 | Correct | 1 ms | 568 KB | Output is correct |
6 | Correct | 2 ms | 568 KB | Output is correct |
7 | Correct | 1 ms | 568 KB | Output is correct |
8 | Correct | 1 ms | 584 KB | Output is correct |
9 | Correct | 37 ms | 1516 KB | Output is correct |
10 | Correct | 13 ms | 1516 KB | Output is correct |
11 | Incorrect | 25 ms | 1516 KB | Output isn't correct |
12 | Halted | 0 ms | 0 KB | - |