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

council

#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';
        }
    }
}

Subtask #1
0 / 8.0

#	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	-

Subtask #2
0 / 8.0

#	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	-

Subtask #3
6.0 / 6.0

#	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

Subtask #4
0 / 19.0

#	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	-

Subtask #5
0 / 15.0

#	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	-

Subtask #6
0 / 22.0

#	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	-

Subtask #7
0 / 22.0

#	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	-

Submission #805748

Compilation message

Subtask #1 0 / 8.0

Subtask #2 0 / 8.0

Subtask #3 6.0 / 6.0

Subtask #4 0 / 19.0

Subtask #5 0 / 15.0

Subtask #6 0 / 22.0

Subtask #7 0 / 22.0

Subtask #1
0 / 8.0

Subtask #2
0 / 8.0

Subtask #3
6.0 / 6.0

Subtask #4
0 / 19.0

Subtask #5
0 / 15.0

Subtask #6
0 / 22.0

Subtask #7
0 / 22.0