제출 #893007

#제출 시각아이디문제언어결과실행 시간메모리
893007vjudge1Chessboard (IZhO18_chessboard)C++17
8 / 100
23 ms7260 KiB
// 以上帝的名义 // 候选硕士 #include <bits/stdc++.h> #ifdef local #include "algo/debug.h" #else #define dbg(x...) 0 #endif using namespace std ; using ll = long long ; #define int ll bool isPrime(int x) { if (x < 2) return 0 ; for (int i = 2 ; i * i <= x ; i++) { if (x % i == 0) { return 0 ; } } return 1 ; } struct Fenwick { vector<ll> t ; int n; Fenwick(int len) { n = len ; t.assign(n + 1, 0) ; } void upd(int i, ll x) { while (i <= n) { t[i] += x; i += (i & (-i)) ; } } ll get(int i) { ll sum = 0 ; while (i) { sum += t[i] ; i -= (i & (-i)) ; } return sum ; } ll get(int l, int r) { return get(r) - get(l - 1) ; } }; int32_t main() { cin.tie(0)->sync_with_stdio(false) ; ll n, k ; cin >> n >> k ; struct rect { int x1, y1, x2, y2; void read() { cin >> x1 >> y1 >> x2 >> y2 ; } }; vector<rect> a(k) ; for (int i = 0 ; i < k ; i++) a[i].read() ; vector<int> d; for (int i = 1 ; i * i <= n ; i++) { if (n % i) continue ; d.push_back(i) ; if (n / i != i) d.push_back(n / i) ; } auto calc = [&](ll del) -> ll{ vector<vector<ll>> cnt(del + 1, vector<ll>(2, 0)) ; int block = n / del ; vector<Fenwick> f(2, Fenwick(n + 2)) ; for (int i = 0 ; i < k ; i++) { int x1 = a[i].x1 , y1 = a[i].y1 , x2 = a[i].x2, y2 = a[i].y2 ; ll leny = (y2 - y1 + 1) ; ll lenx = (x2 - x1 + 1) ; ll bL = (y1 - 1) / block , bR = (y2 - 1) / block ; ll ost = bR - bL - 1 ; ll even = 0 , odd = 0 ; if (ost > 0) { if ((bL + 1) & 1) { even += (ost / 2) * block ; odd += (ost + 1) / 2 * block ; } else { even += (ost + 1) / 2 * block ; odd += (ost / 2) * block ; } } for (int j = y1 - 1 ; j < y2 && j % block != 0 ; j++) { if ((j / block) & 1) { odd++ ; } else { even++ ; } } for (int j = (bR * block + block) ; j < y2 ; j++) { if ((j / block) & 1) { odd++ ; } else { even++ ; } } f[0].upd(x1, even) ; f[0].upd(x2 + 1, -even) ; f[1].upd(x1, odd) ; f[1].upd(x2 + 1, -odd) ; } for (int i = 1 ; i <= n ; i++) { // dbg(f[0].get(i), f[1].get(i)) ; cnt[(i - 1) / block][1] += f[0].get(i) ; cnt[(i - 1) / block][0] += f[1].get(i) ; } // dbg(del, cnt) ; ll ret = 0 , sum = 0 ; for (int i = 0 ; i < del ; i++) { // for (int j = 0 ; j < del ; j++) { if (i % 2 == 0) { ll c = ((del + 1) / 2) * (block * block) ; ll cur = c - cnt[i][0] + cnt[i][1] ; sum += cur ; } else { ll c = (del / 2) * (block * block) ; ll cur = c - cnt[i][1] + cnt[i][0] ; sum += cur ; } // } } ret = sum ; sum = 0 ; for (int i = 0 ; i < del ; i++) { // for (int j = 0 ; j < del ; j++) { if (i % 2 != 0) { ll c = ((del + 1) / 2) * (block * block) ; ll cur = c - cnt[i][0] + cnt[i][1] ; sum += cur ; } else { ll c = (del / 2) * (block * block) ; ll cur = c - cnt[i][1] + cnt[i][0] ; sum += cur ; } // } } ret = min(ret, sum) ; return ret ; }; ll ret = LLONG_MAX ; for (int i : d) { if (i > 1) { ret = min(ret, calc(i)) ; } } cout << ret ; return 0 ; } // 希望白银

컴파일 시 표준 에러 (stderr) 메시지

chessboard.cpp: In lambda function:
chessboard.cpp:75:16: warning: unused variable 'leny' [-Wunused-variable]
   75 |             ll leny = (y2 - y1 + 1) ;
      |                ^~~~
chessboard.cpp:76:16: warning: unused variable 'lenx' [-Wunused-variable]
   76 |             ll lenx = (x2 - x1 + 1) ;
      |                ^~~~
#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...