Submission #926424

#	Time	Username	Problem	Language	Result	Execution time	Memory
926424		AlphaMale06	Chessboard (IZhO18_chessboard)	C++14	100 / 100	674 ms	5716 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;
};

int d;

int get(int x, int y){
    if(x<=0 || y<=0)return 0;
    int x1=x/d;
    int y1=y/d;
    int ret=0;
    if(x1!=0 && y1!=0){
        if(x1&y1&1)ret+=d*d;
    }
    int rx=x-x1*d;
    int ry=y-y1*d;
    if(rx==0 && ry==0)return ret;
    if(y1&1){
        if(x1&1)ret-=d*rx;
        else ret+=d*rx;
    }
    if(x1&1){
       if(y1&1)ret-=d*ry;
        else ret+=d*ry;
    }
    if((x1+y1)&1)ret-=rx*ry;
    else ret+=rx*ry;

    return ret;
}


signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    rect a[k];
    cout << "\n\n";
    for(int i=0; i< k; i++){
        cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2;
    }
    int ans=1e12;
    for(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++){
            flip-=get(a[i].x2, a[i].y2)+get(a[i].x1-1, a[i].y1-1)-get(a[i].x1-1, a[i].y2)-get(a[i].x2, a[i].y1-1);
        }
        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: 30 / 30