Submission #854182

#	Time	Username	Problem	Language	Result	Execution time	Memory
854182		vjudge1	Chessboard (IZhO18_chessboard)	C++17	100 / 100	490 ms	5940 KiB

chessboard

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define int long long
const int maxn=1e5+9;
struct rect{
int x1,y1,x2,y2;
}a[maxn];
long long cal(int len,bool odd){
if (!odd){
    if (len%2==1)len--;
    return (len-2)/2+1;
}
else {
    if (len%2==0)len--;
    return (len-1)/2+1;
}
}
long long x[2];
long long cal(int l,int r,bool odd){
if (odd){
if (r%2==0)r--;
if (l%2==0)l++;
if (l>r)return 0;
return (r-l)/2+1;
}
else {
if (r%2==1)r--;
if (l%2==1)l++;
if (l>r)return 0;
return (r-l)/2+1;
}
}
pair<long long,long long> solve(int x1, int y1,int i){
memset(x,0,sizeof(x));
if ((x1+i-1)/i==(y1+i-1/i)/i){
x[((x1+i-1)/i)%2]+=y1-x1+1;
//cout<<"yay";
}
else {
int len=(x1+i-1)/i;
//cerr<<len<<'\n';
x[len%2]+=(len)*i-x1+1;
x1=(len)*i+1;
x[((y1+i-1)/i)%2]+=(y1)%i;
y1-=(y1%i);
//cout<<x[0]<<" "<<y1<<'\n';
if (x1>y1)return {x[0],x[1]};
int l1=((x1+i-1)/i),l2=y1/i;
x[0]+=1ll*cal(l1,l2,0)*i;
x[1]+=1ll*cal(l1,l2,1)*i;
}
return {x[0],x[1]};
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    long long n;
    int k;
    cin>>n>>k;
    for1(i,1,k)cin>>a[i].x1>>a[i].y1>>a[i].x2>>a[i].y2;
    long long ans=n*n;
    for1(i,1,n-1){
    if (n%i!=0)continue;
    long long len=n/i;
    long long sum=cal(len,1)*cal(len,1)*i*i+cal(len,0)*cal(len,0)*i*i;
    long long sum2=cal(len,1)*cal(len,0)*i*i+cal(len,0)*cal(len,1)*i*i;
    for1(j,1,k){
    int x1=a[j].x1,y1=a[j].y1,x2=a[j].x2,y2=a[j].y2;
    pair<long long,long long>cordx=solve(x1,x2,i),cordy=solve(y1,y2,i);
    //cout<<cordx.fi<<" "<<cordx.se<<" "<<cordy.fi<<" "<<cordy.se<<'\n';
    sum-=cordx.fi*cordy.fi;
    sum-=cordx.se*cordy.se;
    sum+=cordx.fi*cordy.se;
    sum+=cordx.se*cordy.fi;

    sum2+=cordx.fi*cordy.fi;
    sum2+=cordx.se*cordy.se;
    sum2-=cordx.fi*cordy.se;
    sum2-=cordx.se*cordy.fi;
    }
    ans=min(ans,sum);
    ans=min(ans,sum2);
    //cout<<i<<" "<<sum<<" "<<sum2<<'\n';
    }
    cout<<ans;
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 23 / 23
• Subtask 6: 30 / 30