Submission #1134526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134526		ezzzay	Chessboard (IZhO18_chessboard)	C++20	70 / 100	190 ms	2584 KiB

chessboard

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
const int N=3e3;
int a[N][N];
void subtsk1(int n){
    int ans=n*n/2;
    for(int i=1;i<n;i++){
        if(n%i==0){
            int b=n*n/i/i;
            ans=min(ans,b/2*i*i);
        }
    }
    cout<<ans;
}
bool check(int n){
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0)return 0;
    }
    return 1;
}
void subtsk2(int n, int m){
    int a=0;
    int b=0;
    int d=n*n-n*n/2;
    int e=n*n/2;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y>>x>>y;
        if(x%2==y%2){
            a++;
        }
        else{
            b++;
        }
    }
    cout<<min(d-a+b,e-b+a);
    
}
void sbtsk3(int n, int m){
    int ans=n*n;
    vector<pair<int,int>>vc;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y>>x>>y;
        vc.pb({x,y});
    }
    for(int i=1;i<=n/2;i++){
        if(n%i==0){
            int a=0;
            int b=0;
            for(auto p:vc){
                int x=p.ff;
                int y=p.ss;
                int t=i*2;
                if((1<=x%t and x%t<=i and 1<=y%t and y%t<=i) or ( !(1<=x%t and x%t<=i) and !(1<=y%t and y%t<=i))){
                    a++;
                }
                else{
                    b++;
                }
            }
            int bc=n*n/i/i;
            int e=bc/2 * i* i;
            int d=(bc-bc/2)*i*i;
            //cout<<" :: " <<a<<" "<<b<<" "<<d<<" "<<e<<endl;
            
            ans=min(ans,min(d-a+b,e-b+a));
        }
    }
    cout<<ans;
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    
    if(m==0){
        subtsk1(n);
        return 0;
    }
    if(check(n)){
        subtsk2(n,m);
        return 0;
    }
    sbtsk3(n,m);
}

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