Submission #805748

# Submission time Handle Problem Language Result Execution time Memory
805748 2023-08-03T22:29:39 Z someone Council (JOI23_council) C++14
6 / 100
327 ms 8548 KB
#include <bits/stdc++.h>
//#define int long long
using namespace std;

const int M = 1.1e6 + 42;

int n, m, mask[M], occ[M], maxi[M][2];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for(int i = 0; i < n; i++)
        mask[i] = (1 << m) - 1;
    for(int i = 0; i < m; i++)
        occ[i] = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++) {
            int a; cin >> a;
            mask[i] -= a * (1 << j);
            occ[j] += a;
        }
    for(int i = 0; i < (1 << m); i++) {
        maxi[i][0] = M-2;
        maxi[i][1] = M-1;
    }

    for(int i = 0; i < n; i++) {
        if(maxi[mask[i]][0] >= M-2)
            maxi[mask[i]][0] = i;
        else
            maxi[mask[i]][1] = i;
    }
    for(int i = (1 << m)-1; i >= 0; i--) {
        for(int j = 0; j < m; j++) {
            if((i & (1 << j)) == 0) {
                if(maxi[i][0] >= M-2) {
                    maxi[i][0] = maxi[i + (1 << j)][0];
                    maxi[i][1] = maxi[i + (1 << j)][1];
                } else if(maxi[i][1] >= M-2 && maxi[i + (1 << j)][0] != maxi[i][0]) {
                    maxi[i][1] = maxi[i + (1 << j)][0];
                }
            }
        }
    }

    for(int i = 1; i < (1 << m); i++)
        for(int j = 0; j < m; j++)
            if(i & (1 << j)) {
                int id = i ^ (1 << j);
                for(int k = 0; k < 2; k++) {
                    int val = __builtin_popcount(i & mask[maxi[id][0]]);
                    if(maxi[id][k] != maxi[i][0] && maxi[id][k] != maxi[i][1]) {
                        if(val > __builtin_popcount(i & mask[maxi[i][0]])) {
                            maxi[i][1] = maxi[i][0];
                            maxi[i][0] = maxi[id][k];
                        } else if(val > __builtin_popcount(i & mask[maxi[i][1]])) {
                            maxi[i][1] = maxi[id][k];
                        }
                    }
                }
            }

    for(int i = 0; i < n; i++) {
        int bmask = 0, nb = 0;
        for(int j = 0; j < m; j++) {
            if((1 << j) & (mask[i] ^ (1 << j)))
                occ[j]--;
            if(occ[j] == n/2)
                bmask += (1 << j);
            if(occ[j] >= n/2)
                nb++;
            if((1 << j) & (mask[i] ^ (1 << j)))
                occ[j]++;
        }
        if(maxi[bmask][0] != i) {
            cout << nb - __builtin_popcount(bmask ^ (bmask & mask[maxi[bmask][0]])) << '\n';
        } else {
            cout << nb - __builtin_popcount(bmask ^ (bmask & mask[maxi[bmask][1]])) << '\n';
        }
    }
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 188 ms 8532 KB Output is correct
6 Correct 171 ms 8532 KB Output is correct
7 Correct 241 ms 8536 KB Output is correct
8 Correct 316 ms 8532 KB Output is correct
9 Correct 327 ms 8548 KB Output is correct
10 Correct 261 ms 8532 KB Output is correct
11 Correct 318 ms 8532 KB Output is correct
12 Incorrect 325 ms 8532 KB Output isn't correct
13 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 188 ms 8532 KB Output is correct
6 Correct 171 ms 8532 KB Output is correct
7 Correct 241 ms 8536 KB Output is correct
8 Correct 316 ms 8532 KB Output is correct
9 Correct 327 ms 8548 KB Output is correct
10 Correct 261 ms 8532 KB Output is correct
11 Correct 318 ms 8532 KB Output is correct
12 Incorrect 325 ms 8532 KB Output isn't correct
13 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 49 ms 1996 KB Output is correct
3 Correct 43 ms 2020 KB Output is correct
4 Correct 32 ms 2048 KB Output is correct
5 Correct 45 ms 2004 KB Output is correct
6 Correct 31 ms 2032 KB Output is correct
7 Correct 46 ms 1996 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 328 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 49 ms 1996 KB Output is correct
3 Correct 43 ms 2020 KB Output is correct
4 Correct 32 ms 2048 KB Output is correct
5 Correct 45 ms 2004 KB Output is correct
6 Correct 31 ms 2032 KB Output is correct
7 Correct 46 ms 1996 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 328 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 159 ms 7888 KB Output is correct
21 Incorrect 147 ms 7372 KB Output isn't correct
22 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 49 ms 1996 KB Output is correct
3 Correct 43 ms 2020 KB Output is correct
4 Correct 32 ms 2048 KB Output is correct
5 Correct 45 ms 2004 KB Output is correct
6 Correct 31 ms 2032 KB Output is correct
7 Correct 46 ms 1996 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 328 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 159 ms 7888 KB Output is correct
21 Incorrect 147 ms 7372 KB Output isn't correct
22 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 49 ms 1996 KB Output is correct
3 Correct 43 ms 2020 KB Output is correct
4 Correct 32 ms 2048 KB Output is correct
5 Correct 45 ms 2004 KB Output is correct
6 Correct 31 ms 2032 KB Output is correct
7 Correct 46 ms 1996 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 328 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 159 ms 7888 KB Output is correct
21 Incorrect 147 ms 7372 KB Output isn't correct
22 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 188 ms 8532 KB Output is correct
6 Correct 171 ms 8532 KB Output is correct
7 Correct 241 ms 8536 KB Output is correct
8 Correct 316 ms 8532 KB Output is correct
9 Correct 327 ms 8548 KB Output is correct
10 Correct 261 ms 8532 KB Output is correct
11 Correct 318 ms 8532 KB Output is correct
12 Incorrect 325 ms 8532 KB Output isn't correct
13 Halted 0 ms 0 KB -