This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
pair<int,int>vls[N];
void solve(){
cin>>n>>k;
for(int i=1; i<=k; ++i){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
vls[i]={x1,y1};
}vt<int>lst;
for(ll d=1; d*d<=n; ++d){
if(n%d==0){
lst.pb(d);
if(n/d!=d)lst.pb(n/d);
}
}ll ans=INF;
for(int del:lst){
ll heh=n/del;
heh*=heh;
ll cnt=heh-(heh/2),cnt2=heh/2;
cnt*=del*del;
cnt2*=del*del;
//cout<<del<<' '<<cnt<<' '<<cnt2<<endl;
for(int i=1; i<=k; ++i){
ll x,y;
x=vls[i].X;
y=vls[i].Y;
x=(x+(del-1))/del;
y=(y+(del-1))/del;
if(((x+y)%2)==0) {
cnt--;
cnt2++;
}else{
cnt++;
cnt2--;
}
}if(del==n){
ans=min(ans,cnt);
continue;
}
ans=min({ans,cnt,cnt2});
//cout<<del<<' '<<cnt<<' '<<cnt2<<endl;
}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:79:11: warning: unused variable 'lolol' [-Wunused-variable]
79 | int tt=1,lolol=0;
| ^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |