Submission #926322

#TimeUsernameProblemLanguageResultExecution timeMemory
926322AlphaMale06Chessboard (IZhO18_chessboard)C++14
70 / 100
291 ms5856 KiB
#include <bits/stdc++.h> using namespace std; #define F first #define S second #define int long long struct rect{ int x1, y1, x2, y2; }; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, k; cin >> n >> k; rect a[k]; for(int i=0; i< k; i++){ cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2; a[i].x1--; a[i].x2--; a[i].y1--; a[i].y2--; } int ans=1e12; for(int d=1; d<n; d++){ if(n%d!=0)continue; int flip=d*d*(((n*n)/(d*d)+1)/2); for(int i=0; i< k; i++){ int subx1=a[i].x1/d; int subx2=a[i].x2/d; int suby1=a[i].y1/d; int suby2=a[i].y2/d; if(subx1==subx2 && suby1==suby2){ if((subx1&1)==(suby1&1))flip-=(a[i].x2-a[i].x1+1)*(a[i].y2-a[i].y1+1); else flip+=(a[i].x2-a[i].x1+1)*(a[i].y2-a[i].y1+1); } else if(suby1==suby2){ int fali=(subx1+1)*d-1; int fali2=subx2*d; if((subx1&1)==(suby1&1))flip-=(a[i].y2-a[i].y1+1)*(fali-a[i].x1+1); else flip+=(a[i].y2-a[i].y1+1)*(fali-a[i].x1+1); if((subx2&1)==(suby1&1))flip-=(a[i].y2-a[i].y1+1)*(a[i].x2-fali2+1); else flip+=(a[i].y2-a[i].y1+1)*(a[i].x2-fali2+1); int dif=subx2-subx1-1; if(dif%2==0)continue; if((subx1&1)==(suby1&1))flip+=(a[i].y2-a[i].y1+1)*d; else flip-=(a[i].y2-a[i].y1+1)*d; } else if(subx1==subx2){ int fali=(suby1+1)*d-1; int fali2=suby2*d; if((suby1&1)==(subx1&1))flip-=(a[i].x2-a[i].x1+1)*(fali-a[i].y1+1); else flip+=(a[i].x2-a[i].x1+1)*(fali-a[i].y1+1); if((suby2&1)==(subx1&1))flip-=(a[i].x2-a[i].x1+1)*(a[i].y2-fali2+1); else flip+=(a[i].x2-a[i].x1+1)*(a[i].y2-fali2+1); int dif=suby2-suby1-1; if(dif%2==0)continue; if((suby1&1)==(subx1&1))flip+=(a[i].x2-a[i].x1+1)*d; else flip-=(a[i].x2-a[i].x1+1)*d; } else{ if(subx1%2==suby1%2)flip-=(subx1*d-a[i].x1)*(suby1*d-a[i].y1); else flip+=(subx1*d-a[i].x1)*(suby1*d-a[i].y1); if(subx1%2==suby2%2)flip-=(subx1*d-a[i].x1)*(a[i].y2-suby2*d+1); else flip+=(subx1*d-a[i].x1)*(a[i].y2-suby2*d+1); if(subx2%2==suby1%2)flip-=(a[i].x2-subx2*d+1)*(suby1*d-a[i].y1); else flip+=(a[i].x2-subx2*d+1)*(suby1*d-a[i].y1); if(subx2%2==suby2%2)flip-=(a[i].x2-subx2*d+1)*(a[i].y2-suby2*d+1); else flip+=(a[i].x2-subx2*d+1)*(a[i].y2-suby2*d+1); int difx=subx2-subx1-1; int dify=suby2-suby1-1; if(difx%2==0 && dify%2==0)continue; if(dify&1){ if(suby1%2==subx1%2)flip+=d*(subx1*d-a[i].x1); else flip-=d*(subx1*d-a[i].x1); if(suby1%2==subx2%2)flip+=d*(a[i].x2-subx2*d+1); else flip-=d*(a[i].x2-subx2*d+1); } if(difx&1){ if(subx1%2==suby1%2)flip+=d*(suby1*d-a[i].y1); else flip-=d*(suby1*d-a[i].y1); if(subx1%2==suby2%2)flip+=d*(a[i].y2-suby2*d+1); else flip-=d*(a[i].y2-suby2*d+1); } if(subx1%2==suby1%2)flip-=d*d; else flip+=d*d; } } ans=min({ans, flip, n*n-flip}); } cout << ans << '\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...