oj.uz

Submission #741604

# Submission time Handle Problem Language Result Execution time Memory
741604 2023-05-14T13:06:44 Z stevancv Council (JOI23_council) C++14
6 / 100
 222 ms 5320 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 3e5 + 2;
const int K = 12;
const int M = 1 << K;
const ll linf = 1e18;
pair<int, int> mx[M][2], pom[M][2];
vector<int> pos[M];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    int k = n / 2;
    vector<int> a(n), cnt(m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int x; cin >> x;
            if (x == 1) {
                cnt[j] += 1;
                a[i] += 1 << j;
            }
        }
    }
    int www = 0;
    int p = 0, q = 0;
    for (int i = 0; i < m; i++) {
        if (cnt[i] >= k + 2) www++;
        if (cnt[i] == k + 1) p += (1 << i);
        if (cnt[i] == k) q += (1 << i);
    }
    for (int i = 0; i < n; i++) {
        a[i] ^= p ^ q;
        if (pos[a[i]].size() < 2) pos[a[i]].push_back(i);
    }
    /*if (n <= 3000) {
        for (int i = 0; i < n; i++) {
            int mx = 0;
            for (int j = 0; j < n; j++) if (i != j) {
                smax(mx, __builtin_popcount(p & (a[i] | a[j])) + __builtin_popcount(q & (a[i] & a[j])));
            }
            cout << mx + www << en;
        }
        return 0;
    }*/
    for (int mask = M - 1; mask >= 0; mask--) {
        int o = __builtin_popcount(mask);
        pom[mask][0] = pom[mask][1] = {-1, -1};
        for (int i = 0; i < pos[mask].size(); i++) pom[mask][i] = {o, pos[mask][i]};
        for (int i = 0; i < K; i++) {
            int sm = (1 << i) ^ mask;
            if (!((1 << i) & mask)) {
                for (int j = 0; j < 2; j++) {
                    if (pom[sm][j].second != -1 && pom[sm][j].second != pom[mask][1].second) {
                        pom[mask][1] = pom[mask][0];
                        pom[mask][0] = {o, pom[sm][j].second};
                    }
                    else if (pom[sm][j].second != -1 && pom[sm][j].second != pom[mask][0].second) {
                        pom[mask][1] = {o, pom[sm][j].second};
                    }
                }
            }
        }
    }
    for (int mask = 0; mask < M; mask++) {
        mx[mask][0] = mx[mask][1] = {-1, -1};
        for (int smask = mask; smask >= 0; smask = (smask - 1) & mask) {
            for (int j = 0; j < 2; j++) {
                if (pom[smask][j] > mx[mask][0] && pom[smask][j].second != mx[mask][1].second) {
                    mx[mask][1] = mx[mask][0];
                    mx[mask][0] = pom[smask][j];
                }
                else if (pom[smask][j] > mx[mask][1] && pom[smask][j].second != mx[mask][0].second) mx[mask][1] = pom[smask][j];
            }
            if (smask == 0) break;
        }
    }
    for (int i = 0; i < n; i++) {
        int x = a[i] & q;
        int y = a[i] ^ p;
        y &= p;
        x |= y;
        int sol = www;
        sol += __builtin_popcount(a[i] & p);
        if (mx[x][0].second == i && mx[x][1].second != -1) sol += mx[x][1].first;
        else if (mx[x][0].second != -1) sol += mx[x][0].first;
        cout << sol << en;
    }
    return 0;
}

Compilation message

council.cpp: In function 'int main()':
council.cpp:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int i = 0; i < pos[mask].size(); i++) pom[mask][i] = {o, pos[mask][i]};
      |                         ~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 428 KB Output is correct
5 Runtime error 1 ms 596 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 428 KB Output is correct
5 Runtime error 1 ms 596 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 59 ms 2860 KB Output is correct
3 Correct 58 ms 2892 KB Output is correct
4 Correct 40 ms 2644 KB Output is correct
5 Correct 70 ms 2928 KB Output is correct
6 Correct 42 ms 2508 KB Output is correct
7 Correct 59 ms 2840 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 4 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 3 ms 468 KB Output is correct
14 Correct 3 ms 468 KB Output is correct
15 Correct 4 ms 468 KB Output is correct
16 Correct 4 ms 424 KB Output is correct
17 Correct 4 ms 468 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 59 ms 2860 KB Output is correct
3 Correct 58 ms 2892 KB Output is correct
4 Correct 40 ms 2644 KB Output is correct
5 Correct 70 ms 2928 KB Output is correct
6 Correct 42 ms 2508 KB Output is correct
7 Correct 59 ms 2840 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 4 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 3 ms 468 KB Output is correct
14 Correct 3 ms 468 KB Output is correct
15 Correct 4 ms 468 KB Output is correct
16 Correct 4 ms 424 KB Output is correct
17 Correct 4 ms 468 KB Output is correct
18 Correct 3 ms 468 KB Output is correct
19 Correct 3 ms 468 KB Output is correct
20 Incorrect 222 ms 5320 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 59 ms 2860 KB Output is correct
3 Correct 58 ms 2892 KB Output is correct
4 Correct 40 ms 2644 KB Output is correct
5 Correct 70 ms 2928 KB Output is correct
6 Correct 42 ms 2508 KB Output is correct
7 Correct 59 ms 2840 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 4 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 3 ms 468 KB Output is correct
14 Correct 3 ms 468 KB Output is correct
15 Correct 4 ms 468 KB Output is correct
16 Correct 4 ms 424 KB Output is correct
17 Correct 4 ms 468 KB Output is correct
18 Correct 3 ms 468 KB Output is correct
19 Correct 3 ms 468 KB Output is correct
20 Incorrect 222 ms 5320 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 59 ms 2860 KB Output is correct
3 Correct 58 ms 2892 KB Output is correct
4 Correct 40 ms 2644 KB Output is correct
5 Correct 70 ms 2928 KB Output is correct
6 Correct 42 ms 2508 KB Output is correct
7 Correct 59 ms 2840 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 4 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 3 ms 468 KB Output is correct
14 Correct 3 ms 468 KB Output is correct
15 Correct 4 ms 468 KB Output is correct
16 Correct 4 ms 424 KB Output is correct
17 Correct 4 ms 468 KB Output is correct
18 Correct 3 ms 468 KB Output is correct
19 Correct 3 ms 468 KB Output is correct
20 Incorrect 222 ms 5320 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 428 KB Output is correct
5 Runtime error 1 ms 596 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -