제출 #492396

#제출 시각아이디문제언어결과실행 시간메모리
492396phamhoanghiepChessboard (IZhO18_chessboard)C++14
0 / 100
77 ms1208 KiB
#include<bits/stdc++.h> using namespace std; #define fi first #define se second typedef long long ll; typedef pair<int,int> ii; typedef pair<ii,ii> iiii; const int maxn=1e5+5; int n,k; iiii black[maxn]; vector<int> divisors; pair<ll,ll> calc(int d, iiii x) { int cnt_col_0=0; int cnt_col_1=0; int cnt_row_0=0; int cnt_row_1=0; int l_col=x.fi.se/d; int r_col=x.se.se/d; if(l_col==r_col) { if(l_col%2) cnt_col_1=r_col-l_col+1; else cnt_col_0=r_col-l_col+1; } else { int rem_l_col=d-x.fi.se%d; int rem_r_col=x.se.se%d+1; //cout<<"rem col l r "<<rem_l_col<<" "<<rem_r_col<<endl; if(l_col&1) cnt_col_1+=rem_l_col; else cnt_col_0+=rem_l_col; if(r_col&1) cnt_col_1+=rem_r_col; else cnt_col_0+=rem_r_col; } //cout<<"cnt_col 0 1 "<<cnt_col_0<<" "<<cnt_col_1<<endl; l_col++; r_col--; if(l_col<=r_col) { int diff=(r_col-l_col+1); cnt_col_0+=diff*d/2; cnt_col_1+=diff*d/2; if(diff&1) { if(l_col&1) cnt_col_1+=d; else cnt_col_0+=d; } } //cout<<"cnt_col 0 1 "<<cnt_col_0<<" "<<cnt_col_1<<endl; int l_row=x.fi.fi/d; int r_row=x.se.fi/d; if(l_row==r_row) { if(l_row%2) cnt_row_1=r_row-l_row+1; else cnt_row_0=r_row-l_row+1; } else { int rem_l_row=d-x.fi.fi%d; int rem_r_row=x.se.fi%d+1; if(l_row&1) cnt_row_1+=rem_l_row; else cnt_row_0+=rem_l_row; if(r_row&1) cnt_row_1+=rem_r_row; else cnt_row_0+=rem_r_row; } //cout<<"cnt_row 0 1 "<<cnt_row_0<<" "<<cnt_row_1<<endl; l_row++; r_row--; if(l_row<=r_row) { int diff=(r_row-l_row+1); cnt_row_0+=diff*d/2; cnt_row_1+=diff*d/2; if(diff&1) { if(l_row&1) cnt_row_1+=d; else cnt_row_0+=d; } } //cout<<"cnt_row 0 1 "<<cnt_row_0<<" "<<cnt_row_1<<endl; ll a0=1ll*cnt_col_0*cnt_row_0+1ll*cnt_col_1*cnt_row_1; ll a1=1ll*cnt_col_0*cnt_row_1+1ll*cnt_col_1*cnt_row_0; //cout<<"a0 a1 = "<<a0<<" "<<a1<<endl; return make_pair(a0,a1); } ll solve(ll a0, ll a1, int d) { int t=n/d; ll ans=n*n; //cout<<"solve "<<a0<<" "<<a1<<" "<<d<<endl; if(t&1) { ll c0=1ll*t*t/2+1; ll c1=1ll*t*t/2+1; c0*=1ll*d*d; c1*=1ll*d*d; ans=min(a0+c1-a1,a1+c0-a0); swap(c0,c1); ans=min(ans,a0+c1-a1); ans=min(ans,a1+c0-a0); return ans; } else { ll c0=1ll*t*t/2; ll c1=1ll*t*t/2; c0*=1ll*d*d; c1*=1ll*d*d; return min(a0+c1-a1,a1+c0-a0); } } signed main() { cin>>n>>k; for(int i=1 ; i<=k ; i++) { cin>>black[i].fi.fi>>black[i].fi.se>>black[i].se.fi>>black[i].se.se; black[i].fi.fi--; black[i].fi.se--; black[i].se.fi--; black[i].se.se--; } for(int i=1 ; i<n ; i++) { if(n%i==0) { divisors.push_back(i); } } ll ans=n*n; for(int u: divisors) { //cout<<"u = "<<u<<endl; ll a0=0; ll a1=0; for(int i=1 ; i<=k ; i++) { pair<ll,ll> tmp=calc(u,black[i]); a0+=tmp.fi; a1+=tmp.se; } ans=min(ans,solve(a0,a1,u)); } cout<<ans; }
#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...