Submission #851337

#	Time	Username	Problem	Language	Result	Execution time	Memory
851337		vjudge1	Chessboard (IZhO18_chessboard)	C++17	70 / 100	161 ms	3616 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);
        for (int i = 0; i < k; i++) {
                cin >> a[i], a[i]--;
                cin >> b[i], b[i]--;
                int _;
                cin >> _;
                cin >> _;
        }

        int64_t res = 1ll * n * n;
        vector<int64_t> cntb(2, 0);
        vector<int64_t> need(2, 0);
        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;

                for (int j = 0; j < k; j++) {
                        int x = a[j] / i;
                        int y = b[j] / i;
                        cntb[(x ^ y) & 1]++;
                }

                /// (0, 0) white
                res = min(res, cntb[0] + need[1] - cntb[1]);
                res = min(res, need[0] - cntb[0] + cntb[1]);
        }

        cout << res;
}

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