Submission #917281

#	Time	Username	Problem	Language	Result	Execution time	Memory
917281		Sam_a17	Chessboard (IZhO18_chessboard)	C++17	47 / 100	42 ms	9308 KiB

chessboard

//-------------dilanyan------------\\ 
 
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
 
//------------------KarginDefines--------------------\\ 
 
#define ll long long
#define pb push_back
#define all(u) (u).begin(), (u).end()
#define pqueue priority_queue
#define upper upper_bound
#define lower lower_bound
#define umap unordered_map
#define uset unordered_set
#define Kargin ios_base::sync_with_stdio(false);cin.tie(NULL);
#define Usaco freopen(".in", "r", stdin); freopen(".out", "w", stdout);
 
 
//-------------------KarginConstants------------------\\ 
 
const ll mod = 1000000007;
const ll inf = 1e9 + 15;
 
//-------------------KarginCode------------------------\\ 
 
const int N = 1005;
bool a[N][N]; // false -> white true -> black
int pref[2][N][N]; // 0 spitakneri qanaky minchev i,j u 1 severi qanaky
 
bool isprime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}
 
void KarginSolve() {
    long long n, k;
    cin >> n >> k;
    long long sq = sqrt(n);
    vector<int> div{1};
    for (int i = 2;i <= sq;i++) {
        if (n % i == 0) {
            div.pb(i);
            if (i * i != n) div.pb(n / i);
        }
    }
    if (n <= 1000) {
        for (int i = 0; i < k;i++) {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            a[x1][y1] = true;
        }
        for (int i = 1;i <= n;i++) {
            for (int j = 1;j <= n;j++) {
                for (int c = 0;c < 2;c++) {
                    pref[c][i][j] = pref[c][i - 1][j] + pref[c][i][j - 1] - pref[c][i - 1][j - 1] + (a[i][j] == c);
                }
            }
        }
        int ans = n * n / 2;
        for (int d : div) {
            if (d == n) continue;
            int fw = 0, fb = 0;
            for (int i = d, it = 1;i <= n;i += d, it++) {
                for (int j = d, jt = 1;j <= n;j += d, jt++) {
                    if (it & 1) {
                        if (jt & 1) {
                            fb += pref[0][i][j] - pref[0][i - d][j] - pref[0][i][j - d] + pref[0][i - d][j - d];
                            fw += pref[1][i][j] - pref[1][i - d][j] - pref[1][i][j - d] + pref[1][i - d][j - d];
                        }
                        else {
                            fb += pref[1][i][j] - pref[1][i - d][j] - pref[1][i][j - d] + pref[1][i - d][j - d];
                            fw += pref[0][i][j] - pref[0][i - d][j] - pref[0][i][j - d] + pref[0][i - d][j - d];
                        }
                    }
                    else {
                        if (jt & 1) {
                            fb += pref[1][i][j] - pref[1][i - d][j] - pref[1][i][j - d] + pref[1][i - d][j - d];
                            fw += pref[0][i][j] - pref[0][i - d][j] - pref[0][i][j - d] + pref[0][i - d][j - d];
                        }
                        else {
                            fb += pref[0][i][j] - pref[0][i - d][j] - pref[0][i][j - d] + pref[0][i - d][j - d];
                            fw += pref[1][i][j] - pref[1][i - d][j] - pref[1][i][j - d] + pref[1][i - d][j - d];
                        }
                    }
                }
            }
            ans = min(ans, min(fw, fb));
        }
        cout << ans << '\n';
    }
    else if (div.size() == 1) {
        ll fw = n * n / 2, fb = (n * n + 1) / 2;
        for (int i = 0;i < k;i++) {
            int x, y, x1, y1;
            cin >> x >> y >> x1 >> y1;
            if (x & 1) {
                if (y & 1) fb--, fw++;
                else fw--, fb++;
            }
            else {
                if (y & 1) fw--, fb++;
                else fb--, fw++;
            }
        }
        cout << min(fw, fb) << '\n';
    }
}
 
int main() {
    //Usaco
    Kargin;
    int test = 1;
    //cin >> test;
    while (test--) {
        KarginSolve();
    }
    return 0;
}

Compilation message (stderr)

chessboard.cpp:1:1: warning: multi-line comment [-Wcomment]
    1 | //-------------dilanyan------------\\
      | ^
chessboard.cpp:8:1: warning: multi-line comment [-Wcomment]
    8 | //------------------KarginDefines--------------------\\
      | ^
chessboard.cpp:22:1: warning: multi-line comment [-Wcomment]
   22 | //-------------------KarginConstants------------------\\
      | ^
chessboard.cpp:27:1: warning: multi-line comment [-Wcomment]
   27 | //-------------------KarginCode------------------------\\
      | ^

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