Submission #852396

#	Time	Username	Problem	Language	Result	Execution time	Memory
852396		vjudge1	Chessboard (IZhO18_chessboard)	C++17	100 / 100	367 ms	4412 KiB

chessboard

#include <bits/stdc++.h>
using namespace std;

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        int n, k;
        cin >> n >> k;
        vector<int> a(k), b(k), aa(k), bb(k);
        for (int i = 0; i < k; i++) {
                cin >> a[i] >> b[i] >> aa[i] >> bb[i];
                a[i]--, b[i]--, aa[i]--, bb[i]--;
        }

        int64_t res = 1ll * n * n;

        for (int i = 1; i < n; i++) {
                if (n % i) continue;

                vector<int64_t> cntb(2, 0);
                vector<int64_t> need(2, 0);

                need[0] = 1ll * (n / i) * (n / i);
                need[1] = need[0] / 2;
                need[0] -= need[1];
                need[0] *= 1ll * i * i;
                need[1] *= 1ll * i * i;

                auto add_same = [&](int id, int u, int v, int length) {
                        if (u > v) return;
                        int uu = u / i, vv = v / i;
                        if (uu == vv) {
                                cntb[(id ^ uu) & 1] += 1ll * (v - u + 1) * length;
                                return;
                        }
                        assert(uu < vv);
                        int x = i - u % i;
                        cntb[(uu ^ id) & 1] += 1ll * length * x;
                        int y = v % i + 1;
                        cntb[(vv ^ id) & 1] += 1ll * length * y;
                        uu++, vv--;
                        if (uu <= vv) {
                                int64_t addu = 1ll * length * ((vv - uu + 1) / 2 + (((uu ^ vv) & 1) == 0)) * i;
                                cntb[(uu ^ id) & 1] += addu;
                                cntb[(uu ^ id) & 1 ^ 1] += 1ll * (vv - uu + 1) * length * i - addu;
                        }
                };

                auto add = [&](int x, int y, int u, int v) {
                        int up = x / i;
                        int dn = u / i;
                        int lt = y / i;
                        int rt = v / i;
                        if (up == dn) {
                                if (lt == rt) {
                                        cntb[(up ^ lt) & 1] += 1ll * (u - x + 1) * (v - y + 1);
                                } else {
                                        add_same(up, y, v, u - x + 1);
                                }
                        } else {
                                if (lt == rt) {
                                        add_same(lt, x, u, v - y + 1);
                                } else {
                                        add_same(up, y, v, i - x % i);
                                        add_same(dn, y, v, u % i + 1);
                                        add_same(lt, x + (i - x % i), u - (u % i + 1), i - y % i);
                                        add_same(rt, x + (i - x % i), u - (u % i + 1), v % i + 1);
                                        up++, dn--, lt++, rt--;
                                        int64_t p = 1ll * (dn - up + 1) * (rt - lt + 1);
                                        int64_t q = p / 2;
                                        p -= q;
                                        cntb[(up ^ lt) & 1] += 1ll * p * i * i;
                                        cntb[(up ^ lt) & 1 ^ 1] += 1ll * q * i * i;
                                }
                        }
                };

                for (int j = 0; j < k; j++) add(a[j], b[j], aa[j], bb[j]);
                /// (0, 0) white
                res = min(res, cntb[0] + need[1] - cntb[1]);
                res = min(res, need[0] - cntb[0] + cntb[1]);
        }

        cout << res;
}

Compilation message (stderr)

chessboard.cpp: In lambda function:
chessboard.cpp:45:48: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   45 |                                 cntb[(uu ^ id) & 1 ^ 1] += 1ll * (vv - uu + 1) * length * i - addu;
      |                                      ~~~~~~~~~~^~~
chessboard.cpp: In lambda function:
chessboard.cpp:73:56: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   73 |                                         cntb[(up ^ lt) & 1 ^ 1] += 1ll * q * i * i;
      |                                              ~~~~~~~~~~^~~

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 23 / 23
• Subtask 6: 30 / 30