Submission #861611

#	Time	Username	Problem	Language	Result	Execution time	Memory
861611		PagodePaiva	Chessboard (IZhO18_chessboard)	C++17	39 / 100	302 ms	10064 KiB

chessboard

#include<bits/stdc++.h>
#define inf 1e18
#define int long long
#define N 1010

using namespace std;

int v[N][N];
int mark[N][N];

int32_t main(){
    int n, k;
    cin >> n >> k;

    if(n > N-1 or n == 3){
        int res1 = 0;
        int res2 = 0;
        int p = n;

        if(n % 2 == 0){
            res1 = 2;
            res2 = 2;
        }

        else{
            res1 = (p*p+1)/2;
            res2 = (p*p-1)/2;
        }

        for(int i = 1;i <= k;i++){
            int a, b, c, d;
            cin >> a >> b >> c >> d;
            if(a % 2 != b % 2){
                res1--;
                res2++;
            }

            else{
                res1++;
                res2--; 
            }
        }

        cout << min(res1, res2) << '\n';    

        return 0;  
    }


    // vector <pair <int, int>> v;

    for(int i = 1;i <= k;i++){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        v[a][b] = 1;
    }

    int res = inf;

    for(int p = 1;p < n;p++){
        if(n % p != 0) continue;
        int resp = 0;

        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                int ti = (i-1)/p;
                int tj = (j-1)/p;

                if((ti % 2 )!= (tj % 2)){
                    if(v[i][j] != 0) resp++;
                }

                else{
                    if(v[i][j] != 1) resp++;
                }
            }
        }

        // cout << p << ' ' << resp << '\n';
        res = min(res, resp);
        resp = 0;

        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                int ti = (i-1)/p;
                int tj = (j-1)/p;

                if((ti % 2 )!= (tj % 2)){
                    if(v[i][j] != 1) resp++;
                }

                else{
                    if(v[i][j] != 0) resp++;
                }
            }
        }

        res = min(res, resp);
    }

    cout << res << '\n';
}

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