Submission #992509

#TimeUsernameProblemLanguageResultExecution timeMemory
992509tch1cherinChessboard (IZhO18_chessboard)C++17
8 / 100
24 ms5724 KiB
#include <bits/stdc++.h> using namespace std; int main() { cin.tie(nullptr)->sync_with_stdio(false); int N, K; cin >> N >> K; vector<vector<array<int, 3>>> rect(N + 1); for (int i = 0; i < K; i++) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; x1--, y1--, y2--; rect[x1].push_back({y1, y2, 1}); rect[x2].push_back({y1, y2, -1}); } auto Even = [&](int L, int R, int d) { int l = L % (2 * d) >= d ? L + d - L % d : L; int r = R % (2 * d) >= d ? R - R % d - 1 : R; return l > r ? pair {0, -1} : pair {l / (2 * d) * d + l % (2 * d), r / (2 * d) * d + r % (2 * d)}; }; auto Odd = [&](int L, int R, int d) { int l = L % (2 * d) < d ? L + d - L % d : L; int r = R % (2 * d) < d ? R - R % d - 1 : R; return l > r ? pair {0, -1} : pair {l / (2 * d) * d + (l - d) % (2 * d), r / (2 * d) * d + (r - d) % (2 * d)}; }; long long answer = numeric_limits<long long>::max(); for (int d = 1; d < N; d++) { if (N % d == 0) { int N_even = N / (2 * d) * d + min(d, N % (2 * d)), N_odd = N / (2 * d) * d + max(0, N % (2 * d) - d); int cnt_e = 0, cnt_o = 0; long long answer_e = 0, answer_o = 0; for (int i = 0; i < N; i++) { for (auto [j1, j2, t] : rect[i]) { auto [j1_e, j2_e] = Even(j1, j2, d); auto [j1_o, j2_o] = Odd(j1, j2, d); cnt_e += j2_e - j1_e + 1; cnt_o += j2_o - j1_o + 1; } int r = (i / d) % 2; answer_o += (r ? cnt_e : N_even - cnt_e) + (!r ? cnt_o : N_odd - cnt_o); answer_e += (!r ? cnt_e : N_even - cnt_e) + (r ? cnt_o : N_odd - cnt_o); } answer = min({answer, answer_e, answer_o}); } } cout << answer << "\n"; }
#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...