Submission #93088

#TimeUsernameProblemLanguageResultExecution timeMemory
93088MakhsudChessboard (IZhO18_chessboard)C++17
16 / 100
97 ms392 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; ll n, k, x, y, xx, yy; ll mn = INT_MAX; ll ch ( ll del ) { ll ans = 0; if ( del == 1 ) { return (n*n)/2; } for ( int i = 1; i <= (n/del); i ++ ) { if ( i % 2 == 1 ) { ans += (del*del) * ( (n/del) / 2 ); } else { ans += (del*del) * ( ( ( n/del )+1) / 2 ); } } return ans; } ll a[5][5]; void subt2() { for ( int i = 1; i <= k; i ++ ) { cin >> x >> y >> xx >> yy; a[x%2][y%2]++; } ll a1 = 0, a2 = 0; a1 = (n*n) / 2; a2 = a1 + 1; a2 = a2 - (a[1][1] + a[0][0]); a2 = a2 + (a[1][0] + a[0][1]); a1 = a1 - (a[1][0] + a[0][1]); a1 = a1 + (a[1][1] + a[0][0]); cout << min ( (a1), (a2) ); } ll d[50000][5][5]; vector<ll>divs; void subt3() { for ( int i = 1; i < n; i ++ ){ if ( n % i == 0 ){ divs.push_back((ll)i); } } for ( int i = 1; i <= k; i ++ ) { cin >> x >> y >> xx >> yy; for ( auto e: divs ) { ll c, r; r = ( x / e ) + ((x % e) && 1 ); c = ( y / e ) + ((y % e) && 1 ); d[e][r%2][c%2] ++; } } ll cnt1 = 0, cnt2 = 0, mn = INT_MAX; for ( auto e: divs ){ cnt1 = cnt2 = 0; for ( int i = 1; i <= n/e; i ++ ) { if ( i % 2 == 1 ) { cnt1 += ( (e*e) * ((n/e )/2) ); cnt2 += ( (e*e) * (((n/e )/2)+1)); } else { cnt2 += ( (e*e) * ((n/e )/2) ); cnt1 += ( (e*e) * (((n/e )/2)+1)); } } cnt1 += (d[e][1][1] + d[e][0][0]); cnt1 -= (d[e][1][0] + d[e][0][1]); cnt2 += (d[e][1][0] + d[e][0][1]); cnt2 -= (d[e][1][1] + d[e][0][0]); mn = min( mn, min( cnt1, cnt2 ) ); } cout << mn; } int main() { cin >> n >> k; ll cnt = 0; for ( int i = 1; i <= n; i ++ ) if ( n % i == 0 ) cnt ++; if ( cnt == 2 ){ subt2(); return 0; } if ( k != 0 ) { subt3(); return 0; } for ( int i = 1; i < n; i ++ ) { if ( n % i == 0 ) { ll an = ch(i); mn = min ( mn, an ); } } cout << mn; }
#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...