oj.uz

Submission #893370

# Submission time Handle Problem Language Result Execution time Memory
893370 2023-12-27T03:34:42 Z ksujay2 Council (JOI23_council) C++17
33 / 100
 3932 ms 16180 KB 
#include <bits/stdc++.h>
using namespace std;
const int BS = 550;
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int N, M; cin >> N >> M;
    vector<int> A(N);
    vector<int> cnt(M);
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            int a; cin >> a;
            A[i] += a << j;
            cnt[j] += a;
        }
    }
    vector<int> D;
    for(int i = 0; i < N; i++) {
        if(i % BS == 0) {
            D = vector<int>(1 << M, -1);
            queue<int> rep, fut;
            for(int j = 0; j < N; j++) {
                if(j < i || i + BS <= j) {
                    D[A[j]] = 0;
                    fut.push(A[j]);
                }
            }
            while(rep.size() + fut.size() > 0) {
                int s;
                if(rep.size() > 0) s = rep.front(), rep.pop();
                else s = fut.front(), fut.pop();
                for(int j = 0; j < M; j++) {
                    if(D[s ^ (1 << j)] == -1) {
                        if((s & (1 << j)) > 0) {
                            D[s ^ (1 << j)] = D[s] + 1;
                            fut.push(s ^ (1 << j));
                        } else {
                            D[s ^ (1 << j)] = D[s];
                            rep.push(s ^ (1 << j));
                        }
                    }
                }
            }
        }
        int v = 0;
        int ans = 0;
        for(int j = 0; j < M; j++) {
            int c = (cnt[j] - ((A[i] & (1 << j)) > 0));
            if(c == N / 2) {
                v ^= 1 << j;
            }
            if(c >= N / 2) ans++;
        }
        int best = D[(1 << M) - 1 - v];
        if(best == -1) best = 1e9;
        for(int j = i - (i % BS); j < (i + BS - (i % BS)) && j < N; j++) {
            if(j != i) {
                best = min(best, __popcount(A[j] - (A[j] & (~v))));
            }
        }
        cout << ans - best << endl;
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Correct 2 ms 4444 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 456 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 456 KB Output is correct
21 Correct 1 ms 456 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 0 ms 448 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 348 KB Output is correct
46 Correct 1 ms 860 KB Output is correct
47 Correct 0 ms 860 KB Output is correct
48 Correct 1 ms 860 KB Output is correct
49 Correct 1 ms 860 KB Output is correct
50 Correct 0 ms 860 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Correct 2 ms 4444 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 456 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 456 KB Output is correct
21 Correct 1 ms 456 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 0 ms 448 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 348 KB Output is correct
46 Correct 1 ms 860 KB Output is correct
47 Correct 0 ms 860 KB Output is correct
48 Correct 1 ms 860 KB Output is correct
49 Correct 1 ms 860 KB Output is correct
50 Correct 0 ms 860 KB Output is correct
51 Correct 330 ms 9692 KB Output is correct
52 Correct 316 ms 9404 KB Output is correct
53 Correct 327 ms 12116 KB Output is correct
54 Incorrect 311 ms 16180 KB Output isn't correct
55 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2112 ms 4948 KB Output is correct
3 Correct 2101 ms 4848 KB Output is correct
4 Correct 2004 ms 4232 KB Output is correct
5 Correct 2122 ms 4900 KB Output is correct
6 Correct 2024 ms 4128 KB Output is correct
7 Correct 2117 ms 4744 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 388 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 8 ms 348 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2112 ms 4948 KB Output is correct
3 Correct 2101 ms 4848 KB Output is correct
4 Correct 2004 ms 4232 KB Output is correct
5 Correct 2122 ms 4900 KB Output is correct
6 Correct 2024 ms 4128 KB Output is correct
7 Correct 2117 ms 4744 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 388 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 8 ms 348 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 3192 ms 9548 KB Output is correct
21 Correct 3051 ms 9048 KB Output is correct
22 Correct 3150 ms 8936 KB Output is correct
23 Correct 3159 ms 9452 KB Output is correct
24 Correct 3054 ms 9868 KB Output is correct
25 Correct 3265 ms 9828 KB Output is correct
26 Correct 3328 ms 9516 KB Output is correct
27 Correct 0 ms 344 KB Output is correct
28 Correct 0 ms 344 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 456 KB Output is correct
39 Correct 1 ms 348 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 1 ms 348 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2112 ms 4948 KB Output is correct
3 Correct 2101 ms 4848 KB Output is correct
4 Correct 2004 ms 4232 KB Output is correct
5 Correct 2122 ms 4900 KB Output is correct
6 Correct 2024 ms 4128 KB Output is correct
7 Correct 2117 ms 4744 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 388 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 8 ms 348 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 3192 ms 9548 KB Output is correct
21 Correct 3051 ms 9048 KB Output is correct
22 Correct 3150 ms 8936 KB Output is correct
23 Correct 3159 ms 9452 KB Output is correct
24 Correct 3054 ms 9868 KB Output is correct
25 Correct 3265 ms 9828 KB Output is correct
26 Correct 3328 ms 9516 KB Output is correct
27 Correct 0 ms 344 KB Output is correct
28 Correct 0 ms 344 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 456 KB Output is correct
39 Correct 1 ms 348 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 1 ms 348 KB Output is correct
46 Correct 0 ms 348 KB Output is correct
47 Correct 3932 ms 11784 KB Output is correct
48 Incorrect 3542 ms 10904 KB Output isn't correct
49 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2112 ms 4948 KB Output is correct
3 Correct 2101 ms 4848 KB Output is correct
4 Correct 2004 ms 4232 KB Output is correct
5 Correct 2122 ms 4900 KB Output is correct
6 Correct 2024 ms 4128 KB Output is correct
7 Correct 2117 ms 4744 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 388 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 8 ms 348 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 3192 ms 9548 KB Output is correct
21 Correct 3051 ms 9048 KB Output is correct
22 Correct 3150 ms 8936 KB Output is correct
23 Correct 3159 ms 9452 KB Output is correct
24 Correct 3054 ms 9868 KB Output is correct
25 Correct 3265 ms 9828 KB Output is correct
26 Correct 3328 ms 9516 KB Output is correct
27 Correct 0 ms 344 KB Output is correct
28 Correct 0 ms 344 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 456 KB Output is correct
39 Correct 1 ms 348 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 1 ms 348 KB Output is correct
46 Correct 0 ms 348 KB Output is correct
47 Correct 3932 ms 11784 KB Output is correct
48 Incorrect 3542 ms 10904 KB Output isn't correct
49 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Correct 2 ms 4444 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 456 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 456 KB Output is correct
21 Correct 1 ms 456 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 0 ms 448 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 348 KB Output is correct
46 Correct 1 ms 860 KB Output is correct
47 Correct 0 ms 860 KB Output is correct
48 Correct 1 ms 860 KB Output is correct
49 Correct 1 ms 860 KB Output is correct
50 Correct 0 ms 860 KB Output is correct
51 Correct 330 ms 9692 KB Output is correct
52 Correct 316 ms 9404 KB Output is correct
53 Correct 327 ms 12116 KB Output is correct
54 Incorrect 311 ms 16180 KB Output isn't correct
55 Halted 0 ms 0 KB -