oj.uz

답안 #769605

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
769605 2023-06-29T20:38:46 Z MilosMilutinovic Council (JOI23_council) C++14
0 / 100
 1224 ms 98888 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
const int M = 22;
int n, m, a[N][M], b[N][M], v[N], cnt[M], bst[1 << M], ans[N];
void dfs(int i, int x) {
    for (int j = 1; j <= m; j++) {
        int ni = (i ^ (1 << j));
        if (__builtin_popcount(bst[ni] & ni) > __builtin_popcount(x & ni)) {
            bst[ni] = x;
            dfs(ni, x);
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cnt[j] += a[i][j];
        }
    }
    int full_mask = 0;
    for (int j = 1; j <= m; j++) {
        full_mask += (1 << j);
    }
    for (int iter = 1; iter <= 2; iter++) {
        for (int i = 1; i <= n; i++) {
            v[i] = 0;
            for (int j = 1; j <= m; j++) {
                if (a[i][j] == 1) {
                    v[i] += (1 << j);
                }
            }
        }
        for (int i = 0; i < (1 << M); i++) {
            bst[i] = i;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cnt[j] -= a[i][j];
            }
            int msk = 0, good = 0;
            for (int j = 1; j <= m; j++) {
                if (cnt[j] == (n / 2)) {
                    msk ^= (1 << j);
                }
                if (cnt[j] >= (n / 2)) {
                    good += 1;
                }
            }
            ans[iter == 1 ? i : n - i + 1] = max(ans[iter == 1 ? i : n - i + 1], good - __builtin_popcount(bst[msk] & msk));
            for (int j = 1; j <= m; j++) {
                cnt[j] += a[i][j];
            }
            dfs(full_mask ^ v[i], v[i]);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                b[n - i + 1][j] = a[i][j];
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                a[i][j] = b[i][j];
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}

Compilation message

council.cpp: In function 'int main()':
council.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
council.cpp:19:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |             scanf("%d", &a[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 11 ms 16980 KB Output is correct
3 Correct 9 ms 16724 KB Output is correct
4 Correct 9 ms 16724 KB Output is correct
5 Correct 500 ms 98696 KB Output is correct
6 Correct 10 ms 16724 KB Output is correct
7 Correct 706 ms 98888 KB Output is correct
8 Correct 954 ms 98164 KB Output is correct
9 Correct 1162 ms 98792 KB Output is correct
10 Correct 599 ms 98760 KB Output is correct
11 Correct 772 ms 98728 KB Output is correct
12 Correct 1224 ms 98764 KB Output is correct
13 Incorrect 9 ms 16724 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 11 ms 16980 KB Output is correct
3 Correct 9 ms 16724 KB Output is correct
4 Correct 9 ms 16724 KB Output is correct
5 Correct 500 ms 98696 KB Output is correct
6 Correct 10 ms 16724 KB Output is correct
7 Correct 706 ms 98888 KB Output is correct
8 Correct 954 ms 98164 KB Output is correct
9 Correct 1162 ms 98792 KB Output is correct
10 Correct 599 ms 98760 KB Output is correct
11 Correct 772 ms 98728 KB Output is correct
12 Correct 1224 ms 98764 KB Output is correct
13 Incorrect 9 ms 16724 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 16744 KB Output is correct
2 Correct 110 ms 71196 KB Output is correct
3 Correct 107 ms 71240 KB Output is correct
4 Correct 90 ms 71300 KB Output is correct
5 Correct 114 ms 71284 KB Output is correct
6 Incorrect 93 ms 71252 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 16744 KB Output is correct
2 Correct 110 ms 71196 KB Output is correct
3 Correct 107 ms 71240 KB Output is correct
4 Correct 90 ms 71300 KB Output is correct
5 Correct 114 ms 71284 KB Output is correct
6 Incorrect 93 ms 71252 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 16744 KB Output is correct
2 Correct 110 ms 71196 KB Output is correct
3 Correct 107 ms 71240 KB Output is correct
4 Correct 90 ms 71300 KB Output is correct
5 Correct 114 ms 71284 KB Output is correct
6 Incorrect 93 ms 71252 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 16744 KB Output is correct
2 Correct 110 ms 71196 KB Output is correct
3 Correct 107 ms 71240 KB Output is correct
4 Correct 90 ms 71300 KB Output is correct
5 Correct 114 ms 71284 KB Output is correct
6 Incorrect 93 ms 71252 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 11 ms 16980 KB Output is correct
3 Correct 9 ms 16724 KB Output is correct
4 Correct 9 ms 16724 KB Output is correct
5 Correct 500 ms 98696 KB Output is correct
6 Correct 10 ms 16724 KB Output is correct
7 Correct 706 ms 98888 KB Output is correct
8 Correct 954 ms 98164 KB Output is correct
9 Correct 1162 ms 98792 KB Output is correct
10 Correct 599 ms 98760 KB Output is correct
11 Correct 772 ms 98728 KB Output is correct
12 Correct 1224 ms 98764 KB Output is correct
13 Incorrect 9 ms 16724 KB Output isn't correct
14 Halted 0 ms 0 KB -