oj.uz

Submission #892959

# Submission time Handle Problem Language Result Execution time Memory
892959 2023-12-26T09:00:18 Z vjudge1 Chessboard (IZhO18_chessboard) C++17
39 / 100
 211 ms 262144 KB 
// 以上帝的名义
// 候选硕士
#include <bits/stdc++.h>

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

using namespace std ;
using ll = long long ;

int32_t main() {
    cin.tie(0)->sync_with_stdio(false) ;
    int n, k ; cin >> n >> k ;
    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 + 1, vector<vector<int>>(len + 1, 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

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:79:13: note: in expansion of macro 'dbg'
   79 |             dbg(i, calc(i)) ;
      |             ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 968 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 92 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 720 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 856 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 1 ms 1112 KB Output is correct
15 Correct 1 ms 600 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 720 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 856 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 1 ms 1112 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 76 ms 57684 KB Output is correct
17 Correct 85 ms 64168 KB Output is correct
18 Correct 94 ms 64336 KB Output is correct
19 Correct 210 ms 59852 KB Output is correct
20 Correct 211 ms 60164 KB Output is correct
21 Correct 83 ms 64080 KB Output is correct
22 Correct 142 ms 63316 KB Output is correct
23 Correct 106 ms 60324 KB Output is correct
24 Correct 93 ms 63960 KB Output is correct
25 Correct 92 ms 59472 KB Output is correct
26 Correct 85 ms 58512 KB Output is correct
27 Correct 99 ms 60004 KB Output is correct
28 Correct 94 ms 59732 KB Output is correct
29 Correct 68 ms 60316 KB Output is correct
30 Correct 79 ms 61012 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 92 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 968 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Runtime error 92 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -