Submission #685309

#TimeUsernameProblemLanguageResultExecution timeMemory
685309dostigatorChessboard (IZhO18_chessboard)C++17
39 / 100
39 ms9680 KiB
#include <bits/stdc++.h> using namespace std; #define all(a) a.begin(),a.end() #define pb push_back #define vt vector #define endl '\n' #define Y second #define X first typedef long long ll; typedef long double ld; const ll mod=1e9+7; const ll INF=1e18; const int inf=1e9; const int N=2e5+505; const int M=3e3+10; const int dx[]={0,0,1,-1}; const int dy[]={1,-1,0,0}; /*From Benq: stuff you should look for * int overflow, array bounds * special cases (n=1?) * do smth instead of nothing and stay organized * WRITE STUFF DOWN * DON'T GET STUCK ON ONE APPROACH*/ int n,k,used[3000][3000]; void solve(){ cin>>n>>k; for(int i=1; i<=k; ++i){ int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2; used[x1][y1]++; }vt<int>lst; for(int i=1; i<=n; ++i)for(int j=1; j<=n; ++j)used[i][j]+=used[i][j-1]+used[i-1][j]-used[i-1][j-1]; for(int d=1; d*d<=n; ++d){ if(n%d==0){ lst.pb(d); if(n/d!=d)lst.pb(n/d); } }int ans=inf; for(int del:lst){ int cnt=0; int ok=0; int yes=0; //cout<<del<<endl; for(int i=1; i<=n; i+=del){ ++ok; int ok2=0; for(int j=1; j<=n; j+=del){ ++ok2; if((ok+ok2)%2==0){ cnt+=(used[i+del-1][j+del-1]-used[i+del-1][j-1]-used[i-1][j+del-1]+used[i-1][j-1]); continue; } //cout<<del<<' '<<i<<' '<<j<<' '<<(used[i+del-1][j+del-1]-used[i+del-1][j-1]-used[i-1][j+del-1]+used[i-1][j-1])<<endl; yes=1; cnt+=(del*del)-(used[i+del-1][j+del-1]-used[i+del-1][j-1]-used[i-1][j+del-1]+used[i-1][j-1]); } }int cnt2=0; //cout<<endl ok=0; for(int i=1; i<=n; i+=del){ ++ok; int ok2=0; for(int j=1; j<=n; j+=del){ ++ok2; if((ok+ok2)%2){ cnt2+=(used[i+del-1][j+del-1]-used[i+del-1][j-1]-used[i-1][j+del-1]+used[i-1][j-1]); continue; } // cout<<i<<' '<<j<<endl; cnt2+=(del*del)-(used[i+del-1][j+del-1]-used[i+del-1][j-1]-used[i-1][j+del-1]+used[i-1][j-1]); } }//cout<<cnt<<' '<<cnt2<<endl; ans=min({ans,cnt2}); if(yes)ans=min(ans,cnt); }cout<<ans<<endl; } int main(){ //srand(time(0)); //freopen("hotel.in","r",stdin); //freopen("hotel.out","w",stdout); ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int tt=1,lolol=0; // cin>>tt; while(tt--) { //cout<<"Case "<<++lolol<<": "; solve(); } }

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:89:11: warning: unused variable 'lolol' [-Wunused-variable]
   89 |  int tt=1,lolol=0;
      |           ^~~~~
#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...