Submission #379855

#TimeUsernameProblemLanguageResultExecution timeMemory
379855KalashnikovChessboard (IZhO18_chessboard)C++17
100 / 100
801 ms5996 KiB
#include <bits/stdc++.h> #define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout) #define all(a) a.begin() , a.end() #define F first #define S second using namespace std; using ll = long long; #define y1 dsfsdf #define int ll const int N = 2e5+5 , inf = 2e9 + 7; const ll INF = 1e18 , mod = 1e9+7 , P = 6547; int x1[N] , y1[N] , x2[N] , y2[N]; void solve() { ll n, k; cin >> n >> k; if(k == 0) { ll ans = n*n / 2; for(int i = 2; i < n; i ++) { if(n%i == 0) { int x = i; if((n/x) % 2) { ans = min(ans , (n/x) * (n/x) / 2 * x*x); } } } cout << ans; return; } ll blacks = 0; for(int i = 1; i <= k; i ++) { cin >> x1[i] >> y1[i] >> x2[i] >> y2[i]; blacks += (x2[i]-x1[i]+1) * (y2[i]-y1[i]+1); x1[i] --; x2[i] --; y1[i] --; y2[i] --; } ll ans = n*n; for(int i = 1; i < n; i ++) { if(n%i == 0) { int RightBlacks = 0; for(int j = 1; j <= k; j ++) { int cnt[2] , cnt1[2]; fill(cnt , cnt+2 , 0); fill(cnt1 , cnt1+2 , 0); { int l = x1[j], r = x2[j]; int l1 = l/i*i+i , r1 = r/i*i-1; if(l1 <= r1) { assert((r1-l1+1) % i == 0); int col = (r1-l1+1) / i; cnt[0] = col/2 * i; cnt[1] = col/2 * i; if(col%2) { cnt[l1/i % 2] += i; } cnt[l/i % 2] += l1-l; cnt[r/i % 2] += (r-r1); } else { int l1 = l , r1 = r , res; while(l1 <= r1) { int md = l1+r1 >> 1; if(l/i%2 == md/i%2) { res = md; l1 = md+1; } else { r1 = md-1; } } cnt[l/i%2] += res-l+1; cnt[r/i%2] += r-res; } } { int l = y1[j], r = y2[j]; int l1 = l/i*i+i , r1 = r/i*i-1; if(l1 <= r1) { assert((r1-l1+1) % i == 0); int col = (r1-l1+1) / i; cnt1[0] = col/2 * i; cnt1[1] = col/2 * i; if(col%2) { cnt1[l1/i % 2] += i; } cnt1[l/i % 2] += l1-l; cnt1[r/i % 2] += (r-r1); } else { int l1 = l , r1 = r , res; while(l1 <= r1) { int md = l1+r1 >> 1; if(l/i%2 == md/i%2) { res = md; l1 = md+1; } else { r1 = md-1; } } cnt1[l/i%2] += res-l+1; cnt1[r/i%2] += r-res; } } RightBlacks += cnt[0] * cnt1[0]; RightBlacks += cnt[1] * cnt1[1]; } int a = (n/i)*(n/i) / 2 * i*i; int b = a; if((n/i) % 2) { a += i*i; } ans = min(ans , a-RightBlacks + (blacks - RightBlacks)); ans = min(ans , b-(blacks - RightBlacks) + RightBlacks); } } cout << ans; } /* */ main() { ios; int tt = 1; //cin >> tt; while(tt --) { solve(); } return 0; }

Compilation message (stderr)

chessboard.cpp: In function 'void solve()':
chessboard.cpp:71:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |        int md = l1+r1 >> 1;
      |                 ~~^~~
chessboard.cpp:102:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |        int md = l1+r1 >> 1;
      |                 ~~^~~
chessboard.cpp: At global scope:
chessboard.cpp:132:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  132 | main() {
      |      ^
chessboard.cpp: In function 'void solve()':
chessboard.cpp:112:23: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  112 |       cnt1[r/i%2] += r-res;
      |                      ~^~~~
chessboard.cpp:81:22: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |       cnt[r/i%2] += r-res;
      |                     ~^~~~
#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...