# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
378551 | 2021-03-17T01:42:28 Z | 2qbingxuan | Chessboard (IZhO18_chessboard) | C++14 | 2000 ms | 1260 KB |
#include <bits/stdc++.h> #ifdef local #define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n" #define debug(a...) qqbx(#a, a) template <typename ...T> void qqbx(const char *s, T ...a) { int cnt = sizeof...(T); ((std::cerr << "\033[1;32m(" << s << ") = (") , ... , (std::cerr << a << (--cnt ? ", " : ")\033[0m\n"))); } #else #define safe ((void)0) #define debug(...) ((void)0) #endif // local using namespace std; using ll = int64_t; const int maxn = 100025; const ll INF = 1e18; bool isBlack(int x, int y) { return (x + y) & 1; } ll calc2d(int x, int y, int k, bool c) { if (x < 0 || y < 0) return 0; ll qx = x / k, rx = x % k; ll qy = y / k, ry = y % k; ll ans = 0; ans += ry * k * (isBlack(0, qy) == c ? (qx + 1) / 2 : qx / 2); ans += rx * k * (isBlack(qx, 0) == c ? (qy + 1) / 2 : qy / 2); ans += k * k * (isBlack(0, 0) == c ? (qx * qy + 1) / 2 : qx * qy / 2); if (isBlack(qx, qy) == c) ans += rx * ry; int res = 0; for (int i = 0; i <= x; i++) for (int j = 0; j <= y; j++) if (((i / k) + (j / k)) % 2 == c) ++res; debug(x, y, k, c, ans, res); return res; return ans; } ll calc(int L, vector<tuple<int,int,int,int>> &v, int k) { ll res = INF; for (int c: {0, 1}) { cerr << "============\n"; ll ans = calc2d(L-1, L-1, k, c); for (auto [lx, ly, rx, ry]: v) { debug(lx, ly, rx, ry); ans += (rx - lx) * (ry - ly); ans -= 2 * (calc2d(rx, ry, k, c) - calc2d(rx, ly, k, c) - calc2d(lx, ry, k, c) + calc2d(lx, ly, k, c)); } debug(ans, k, c); res = min(ans, res); } return res; } signed main() { ios_base::sync_with_stdio(0), cin.tie(0); int L, n; cin >> L >> n; vector<tuple<int,int,int,int>> rect(n); for (auto &[a, b, c, d]: rect) cin >> a >> b >> c >> d, --a, --b, --a, --b, --c, --d; ll ans = INF; for (int i = 1; i*i <= L; i++) { if (L % i == 0) { if (i != L) ans = min(ans, calc(L, rect, i)); if (L/i != L) ans = min(ans, calc(L, rect, L / i)); } if (i*i > L) break; } cout << ans << '\n'; } /* 6 8 3 3 3 3 1 2 1 2 3 4 3 4 5 5 5 5 4 3 4 3 4 4 4 4 2 1 2 1 3 6 3 6 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 2 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 2 ms | 364 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2091 ms | 1260 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 151 ms | 400 KB | Output is correct |
2 | Correct | 18 ms | 364 KB | Output is correct |
3 | Correct | 128 ms | 364 KB | Output is correct |
4 | Correct | 480 ms | 492 KB | Output is correct |
5 | Correct | 174 ms | 420 KB | Output is correct |
6 | Correct | 132 ms | 492 KB | Output is correct |
7 | Correct | 241 ms | 492 KB | Output is correct |
8 | Correct | 158 ms | 492 KB | Output is correct |
9 | Correct | 119 ms | 412 KB | Output is correct |
10 | Correct | 8 ms | 364 KB | Output is correct |
11 | Correct | 94 ms | 492 KB | Output is correct |
12 | Correct | 19 ms | 364 KB | Output is correct |
13 | Correct | 287 ms | 492 KB | Output is correct |
14 | Correct | 307 ms | 492 KB | Output is correct |
15 | Correct | 93 ms | 364 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 151 ms | 400 KB | Output is correct |
2 | Correct | 18 ms | 364 KB | Output is correct |
3 | Correct | 128 ms | 364 KB | Output is correct |
4 | Correct | 480 ms | 492 KB | Output is correct |
5 | Correct | 174 ms | 420 KB | Output is correct |
6 | Correct | 132 ms | 492 KB | Output is correct |
7 | Correct | 241 ms | 492 KB | Output is correct |
8 | Correct | 158 ms | 492 KB | Output is correct |
9 | Correct | 119 ms | 412 KB | Output is correct |
10 | Correct | 8 ms | 364 KB | Output is correct |
11 | Correct | 94 ms | 492 KB | Output is correct |
12 | Correct | 19 ms | 364 KB | Output is correct |
13 | Correct | 287 ms | 492 KB | Output is correct |
14 | Correct | 307 ms | 492 KB | Output is correct |
15 | Correct | 93 ms | 364 KB | Output is correct |
16 | Execution timed out | 2098 ms | 1260 KB | Time limit exceeded |
17 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2091 ms | 1260 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 2 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 2 ms | 364 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Execution timed out | 2091 ms | 1260 KB | Time limit exceeded |
10 | Halted | 0 ms | 0 KB | - |