Submission #92973

#TimeUsernameProblemLanguageResultExecution timeMemory
92973MakhsudChessboard (IZhO18_chessboard)C++17
31 / 100
100 ms504 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; ll n, k, x, y, xx, yy; ll d, 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) ); } bool used[105][105]; ll NumOfPainted( ll s, ll e, ll de ) { ll num = 0; for ( int i = s; i <= s+de-1; i ++ ){ for ( int j = e; j <= e+de-1; j ++ ) { if ( used[i][j] ) num ++; } } return num; } ll subt3( ll del ) { ll cnt1 = 0, cnt2 = 0, c=0, d=0; for ( int i = 1; i <= n; i += del ) { c ++; for ( int j = 1; j <= n; j += del ) { d ++; if ( (c % 2 == 1 && d % 2 == 0) || (c % 2 == 0 && d % 2 == 1) ) { cnt1 += ( (del*del) - NumOfPainted(i,j,del) ); cnt2 += NumOfPainted(i,j,del); } if ( (c % 2 == 1 && d % 2 == 1) || (c % 2 == 0 && d % 2 == 0) ) { cnt1 += NumOfPainted(i,j,del); cnt2 += ( (del*del) - NumOfPainted(i,j,del) ); } } d = 0; } return min(cnt1,cnt2); } 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 ) { ll MN = INT_MAX; for ( int i = 1; i <= k; i ++ ) { cin >> x >> y >> xx >> yy; used[x][y] = true; } for ( int i = 1; i < n; i ++ ) { if ( n % i == 0 ) { ll an = subt3(i); //cout << an << '\n'; MN = min (MN, an); } } cout << MN; 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...