Submission #892964

#	Time	Username	Problem	Language	Result	Execution time	Memory
892964		vjudge1	Chessboard (IZhO18_chessboard)	C++17	47 / 100	212 ms	262144 KiB

chessboard

// 以上帝的名义
// 候选硕士
#include <bits/stdc++.h>

#ifdef local
#include "algo/debug.h"
#else
#define dbg(x...) 0
#endif

using namespace std ;
using ll = long long ;

bool isPrime(int x) {
    if (x < 2) return 0 ;
    for (int i = 2 ; i * i <= x ; i++) {
        if (x  % i == 0) {
            return 0 ;
        }
    }
    return 1 ;
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(false) ;
    ll n, k ; cin >> n >> k ;
    if (isPrime(n)) {
        vector<vector<ll>> row(n + 1, vector<ll>(2, 0)) ;
        auto black = row , white = row ;
        while (k--) {
            int x1 , y1 , x2,  y2 ;cin >> x1 >> y1 >> x2 >> y2 ;
            row[x1][y1 % 2]++ ;
            black[x1][y1 % 2]++ ;
        }
        ll ret = 0 , sum = 0 ;
        for (int i = 1 ; i <= n ; i++) {
            if (i & 1) {
                ll len = (n + 1) / 2 ;
                ll cur = len - black[i][i % 2] + black[i][!(i % 2)] ;
                sum += cur ;
            } else {
                ll len = (n / 2) ;
                ll cur = len - black[i][i % 2] + black[i][!(i % 2)] ;
                sum += cur ;

            }
        }
        ret = sum ; sum = 0 ;
        for (int i = 1 ; i <= n ; i++) {
            if (i & 1) {
                ll len = (n) / 2 ;
                ll cur = len - black[i][!(i % 2)] + black[i][(i % 2)] ;
                sum += cur ;
            } else {
                ll len = ((n + 1) / 2) ;
                ll cur = len - black[i][!(i % 2)] + black[i][(i % 2)] ;
                sum += cur ;

            }
        }
        ret = min(ret, sum) ;
        cout << ret ;
        return 0 ;
    }
    vector<vector<int>> a(n + 2, vector<int>(n + 2, 0)) ;
    auto b = a ;
    for (int i = 0 ; i < k ; i++) {
        int x1 , y1 , x2 , y2 ; cin >> x1 >> y1 >> x2 >> y2 ;
        a[x1][y1]++ , a[x1][y2 + 1]-- ;
        a[x2 + 1][y1]-- , a[x2 + 1][y2 + 1]++ ;
    }
    for (int i = 1 ; i <= n ; i++) {
        for (int j = 1 ; j <= n ; j++) {
            a[i][j] += a[i - 1][j] ;
            a[i][j] += a[i][j - 1] ;
            a[i][j] -= a[i - 1][j - 1] ;
            a[i][j] = bool (a[i][j]) ;
            b[i][j] = b[i - 1][j] + b[i][j - 1] + a[i][j] - b[i - 1][j - 1] ;
        }
    }
    vector<int> d;
    for (int i = 1 ; i * i <= n ; i++) {
        if (n % i) continue ;
        d.push_back(i) ;
        if (n / i != i) d.push_back(n / i) ;
    }
    auto calc = [&](int len) -> int {
        int N = n / len ;
        vector<vector<vector<int>>> c(len + 3, vector<vector<int>>(len + 3, vector<int>(2 ,0))) ;
        for (int i = 1 ; i <= n ; i++) {
            for (int j = 1 ; j <= n ; j++) {
                c[(i - 1) / N][(j - 1) / N][a[i][j]]++ ;
            }
        }
        ll cur = 0 , ret = 0 ;
        for (int i = 0 ; i < len ; i++) {
            for (int j = 0 ; j < len ; j++) {
//                dbg(i, j, c[i][j][0], c[i][j][1]) ;
                if ((i % 2) != (j % 2)) {
                    ll sum = N * N - c[i][j][1] ;
                    cur += sum ;
                } else {
                    ll sum = N * N - c[i][j][0] ;
                    cur += sum ;
                }
            }
        }
        ret = cur , cur = 0 ;
        for (int i = 0 ; i < len ; i++) {
            for (int j = 0 ; j < len ; j++) {
                if ((i % 2) == (j % 2)) {
                    ll sum = N * N - c[i][j][1] ;
                    cur += sum ;
                } else {
                    ll sum = N * N - c[i][j][0] ;
                    cur += sum ;
                }
            }
        }
        ret = min(ret, cur) ;
        return ret ;
    };
    sort(d.begin(), d.end()) ;
    int ret = INT_MAX ;
    for (int i : d) {
        if (i > 1) {
            dbg(i, calc(i)) ;
            ret = min(ret, calc(i)) ;
        }
    }
    cout << ret ;
    return 0 ;
}

// 希望白银

Compilation message (stderr)

chessboard.cpp: In function 'int32_t main()':
chessboard.cpp:8:19: warning: statement has no effect [-Wunused-value]
    8 | #define dbg(x...) 0
      |                   ^
chessboard.cpp:127:13: note: in expansion of macro 'dbg'
  127 |             dbg(i, calc(i)) ;
      |             ^~~

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