oj.uz

답안 #769602

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
769602 2023-06-29T20:36:36 Z MilosMilutinovic Council (JOI23_council) C++14
0 / 100
 1251 ms 90584 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
const int M = 21;
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 5 ms 8532 KB Output is correct
2 Correct 6 ms 8788 KB Output is correct
3 Correct 4 ms 8532 KB Output is correct
4 Correct 4 ms 8532 KB Output is correct
5 Correct 504 ms 90584 KB Output is correct
6 Correct 5 ms 8532 KB Output is correct
7 Correct 693 ms 90548 KB Output is correct
8 Correct 1002 ms 89952 KB Output is correct
9 Correct 1178 ms 90456 KB Output is correct
10 Correct 586 ms 90560 KB Output is correct
11 Correct 761 ms 90464 KB Output is correct
12 Correct 1251 ms 90492 KB Output is correct
13 Incorrect 5 ms 8532 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8532 KB Output is correct
2 Correct 6 ms 8788 KB Output is correct
3 Correct 4 ms 8532 KB Output is correct
4 Correct 4 ms 8532 KB Output is correct
5 Correct 504 ms 90584 KB Output is correct
6 Correct 5 ms 8532 KB Output is correct
7 Correct 693 ms 90548 KB Output is correct
8 Correct 1002 ms 89952 KB Output is correct
9 Correct 1178 ms 90456 KB Output is correct
10 Correct 586 ms 90560 KB Output is correct
11 Correct 761 ms 90464 KB Output is correct
12 Correct 1251 ms 90492 KB Output is correct
13 Incorrect 5 ms 8532 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8504 KB Output is correct
2 Correct 127 ms 60720 KB Output is correct
3 Correct 103 ms 60652 KB Output is correct
4 Correct 85 ms 60660 KB Output is correct
5 Correct 110 ms 60756 KB Output is correct
6 Incorrect 93 ms 60740 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8504 KB Output is correct
2 Correct 127 ms 60720 KB Output is correct
3 Correct 103 ms 60652 KB Output is correct
4 Correct 85 ms 60660 KB Output is correct
5 Correct 110 ms 60756 KB Output is correct
6 Incorrect 93 ms 60740 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8504 KB Output is correct
2 Correct 127 ms 60720 KB Output is correct
3 Correct 103 ms 60652 KB Output is correct
4 Correct 85 ms 60660 KB Output is correct
5 Correct 110 ms 60756 KB Output is correct
6 Incorrect 93 ms 60740 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8504 KB Output is correct
2 Correct 127 ms 60720 KB Output is correct
3 Correct 103 ms 60652 KB Output is correct
4 Correct 85 ms 60660 KB Output is correct
5 Correct 110 ms 60756 KB Output is correct
6 Incorrect 93 ms 60740 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8532 KB Output is correct
2 Correct 6 ms 8788 KB Output is correct
3 Correct 4 ms 8532 KB Output is correct
4 Correct 4 ms 8532 KB Output is correct
5 Correct 504 ms 90584 KB Output is correct
6 Correct 5 ms 8532 KB Output is correct
7 Correct 693 ms 90548 KB Output is correct
8 Correct 1002 ms 89952 KB Output is correct
9 Correct 1178 ms 90456 KB Output is correct
10 Correct 586 ms 90560 KB Output is correct
11 Correct 761 ms 90464 KB Output is correct
12 Correct 1251 ms 90492 KB Output is correct
13 Incorrect 5 ms 8532 KB Output isn't correct
14 Halted 0 ms 0 KB -