Submission #926344

#	Time	Username	Problem	Language	Result	Execution time	Memory
926344		AlphaMale06	Chessboard (IZhO18_chessboard)	C++14	70 / 100	294 ms	3672 KiB

chessboard

#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second
#define int long long

struct rect{
    int x1, y1, x2, y2;
};

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    rect a[k];
    for(int i=0; i< k; i++){
        cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2;
        a[i].x1--;
        a[i].x2--;
        a[i].y1--;
        a[i].y2--;
    }
    int ans=1e12;
    for(int d=1; d<n; d++){
        if(n%d!=0)continue;
        int flip=d*d*(((n*n)/(d*d)+1)/2);
        for(int i=0; i< k; i++){
            int subx1=a[i].x1/d;
            int subx2=a[i].x2/d;
            int suby1=a[i].y1/d;
            int suby2=a[i].y2/d;
            //tretiras ovaj case isto kao i 1x1 kvadrate, jer skroz spadaju u to
            if(subx1==subx2 && suby1==suby2){
                if((subx1&1)==(suby1&1))flip-=(a[i].x2-a[i].x1+1)*(a[i].y2-a[i].y1+1);
                else flip+=(a[i].x2-a[i].x1+1)*(a[i].y2-a[i].y1+1);
                continue;
            }
            //kad nije u samo jednom dxd polju
            if(subx1==subx2){//kad je samo po y vise polja
                int dify=suby2-suby1-1; //broj polja izmedju
                if(dify&1){//ako je neparno onda utice na score
                    if(subx1%2==suby1%2){//u ovom slucaju pravougaonik koji pokrivas ima jedno vise belo nego crno dxd
                        flip+=d*(a[i].x2-a[i].x1+1);
                    }
                    else{ //u suprotnom jedno vise crno dxd
                        flip-=d*(a[i].x2-a[i].x1+1);
                    }
                }
                //sad treba samo ove otsecke
                if(subx1%2==suby1%2){
                    flip-=(a[i].x2-a[i].x1+1)*((suby1+1)*d-a[i].y1);
                }
                else{
                    flip+=(a[i].x2-a[i].x1+1)*((suby1+1)*d-a[i].y1);
                }
                if(subx1%2==suby2%2){
                    flip-=(a[i].x2-a[i].x1+1)*(a[i].y2-suby2*d+1);
                }
                else{
                    flip+=(a[i].x2-a[i].x1+1)*(a[i].y2-suby2*d+1);
                }
            }
            else if(suby1==suby2){//kad je samo po x vise polja
                int difx=subx2-subx1-1; //broj polja izmedju
                if(difx&1){//ako je neparno onda utice na score
                    if(suby1%2==subx1%2){//u ovom slucaju pravougaonik koji pokrivas ima jedno vise belo nego crno dxd
                        flip+=d*(a[i].y2-a[i].y1+1);
                    }
                    else{ //u suprotnom jedno vise crno dxd
                        flip-=d*(a[i].y2-a[i].y1+1);
                    }
                }
                //sad treba samo ove otsecke
                if(suby1%2==subx1%2){
                    flip-=(a[i].y2-a[i].y1+1)*((subx1+1)*d-a[i].x1);
                }
                else{
                    flip+=(a[i].y2-a[i].y1+1)*((subx1+1)*d-a[i].x1);
                }
                if(suby1%2==subx2%2){
                    flip-=(a[i].y2-a[i].y1+1)*(a[i].x2-subx2*d+1);
                }
                else{
                    flip+=(a[i].y2-a[i].y1+1)*(a[i].x2-subx2*d+1);
                }
            }
            else{//kad je vise polja i po x i po y
                //oduzmes/dodas coskove
                if(subx1%2==suby1%2){
                    flip-=((subx1+1)*d-a[i].x1)*((suby1+1)*d-a[i].y1);
                }
                else{
                    flip+=((subx1+1)*d-a[i].x1)*((suby1+1)*d-a[i].y1);
                }
                if(subx1%2==suby2%2){
                    flip-=((subx1+1)*d-a[i].x1)*(a[i].y2-suby2*d+1);
                }
                else{
                    flip+=((subx1+1)*d-a[i].x1)*(a[i].y2-suby2*d+1);
                }
                if(subx2%2==suby1%2){
                    flip-=(a[i].x2-subx2*d+1)*((suby1+1)*d-a[i].y1);
                }
                else{
                    flip+=(a[i].x2-subx2*d+1)*((suby1+1)*d-a[i].y1);
                }
                if(subx2%2==suby2%2){
                    flip-=(a[i].x2-subx2*d+1)*(a[i].y2-suby2*d+1);
                }
                else{
                    flip+=(a[i].x2-subx2*d+1)*(a[i].y2-suby2*d+1);
                }
                //ivice
                int difx=subx2-subx1-1;
                int dify=suby2-suby1-1;
                if(difx%2==1){//ako ivice po x-u doprinose nesto
                    if(subx1%2!=suby1%2){
                        flip-=((suby1+1)*d-a[i].y1)*d;
                    }
                    else{
                        flip+=((suby1+1)*d-a[i].y1)*d;
                    }
                    if(subx1%2!=suby2%2){
                        flip-=(a[i].y2-suby2*d+1)*d;
                    }
                    else{
                        flip+=(a[i].y2-suby2*d+1)*d;
                    }
                }
                if(dify%2==1){//ako ivice po y-u doprinose nesto
                    if(suby1%2!=subx1%2){
                        flip-=((subx1+1)*d-a[i].x1)*d;
                    }
                    else{
                        flip+=((subx1+1)*d-a[i].x1)*d;
                    }
                    if(suby1%2!=subx2%2){
                        flip-=(a[i].x2-subx2*d+1)*d;
                    }
                    else{
                        flip+=(a[i].x2-subx2*d+1)*d;
                    }
                }
                if(difx%2==0 && dify%2==0){//ako deo u sredini doprinosi nesto
                    if(subx1%2==suby1%2){
                        flip-=d*d;
                    }
                    else flip+=d*d;
                }
            }
        }
        ans=min({ans, flip, n*n-flip});
    }
    cout << ans << '\n';
}

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