oj.uz

Submission #637245

# Submission time Handle Problem Language Result Execution time Memory
637245 2022-09-01T06:53:02 Z tvladm2009 Norela (info1cup18_norela) C++14
100 / 100
 141 ms 197272 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long long ld;

const int MAX_N = 60;
const int MAX_M = 24;

ll spells[MAX_N + 1], cards[1ll << MAX_M];
int lg2[1 << MAX_M];
vector<int> mn;

int n, m;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int q;
        cin >> q;
        while (q--) {
            int x;
            cin >> x;
            x--;
            spells[i] |= (1ll << x);
        }
    }

    for (int i = 2; i < (1ll << m); i++) {
        lg2[i] = lg2[i >> 1] + 1;
    }
    for (int mask = 1; mask < (1 << m); mask++) {
        int bit = lg2[(mask & -mask)];
        cards[mask] = (cards[mask ^ (1ll << bit)] ^ spells[bit + 1]);
    }
    int answer = (1 << 30);
    for (int mask = 0; mask < (1 << m); mask++) {
        if (cards[mask] == (1ll << n) - 1) {
            answer = min(answer, __builtin_popcountll(mask));
        }
    }

    cout << answer << "\n";
    for (int mask = 0; mask < (1 << m); mask++) {
        if (cards[mask] == (1ll << n) - 1 && __builtin_popcountll(mask) == answer) {
            vector<int> used;
            for (int bit = 0; bit < m; bit++) {
                if (mask & (1 << bit)) {
                    used.push_back(bit + 1);
                }
            }
            if (mn.size() == 0 || used < mn) {
                mn = used;
            }
        }
    }
    for (int it : mn) {
        cout << it << " ";
    }

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 3 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 3 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 9 ms 12628 KB Output is correct
8 Correct 19 ms 24952 KB Output is correct
9 Correct 18 ms 24940 KB Output is correct
10 Correct 18 ms 24916 KB Output is correct
11 Correct 21 ms 24916 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 3 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 9 ms 12628 KB Output is correct
8 Correct 19 ms 24952 KB Output is correct
9 Correct 18 ms 24940 KB Output is correct
10 Correct 18 ms 24916 KB Output is correct
11 Correct 21 ms 24916 KB Output is correct
12 Correct 20 ms 24856 KB Output is correct
13 Correct 35 ms 49564 KB Output is correct
14 Correct 36 ms 49496 KB Output is correct
15 Correct 38 ms 49616 KB Output is correct
16 Correct 34 ms 49536 KB Output is correct
17 Correct 35 ms 49448 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 3 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 9 ms 12628 KB Output is correct
8 Correct 19 ms 24952 KB Output is correct
9 Correct 18 ms 24940 KB Output is correct
10 Correct 18 ms 24916 KB Output is correct
11 Correct 21 ms 24916 KB Output is correct
12 Correct 20 ms 24856 KB Output is correct
13 Correct 35 ms 49564 KB Output is correct
14 Correct 36 ms 49496 KB Output is correct
15 Correct 38 ms 49616 KB Output is correct
16 Correct 34 ms 49536 KB Output is correct
17 Correct 35 ms 49448 KB Output is correct
18 Correct 67 ms 98780 KB Output is correct
19 Correct 70 ms 98764 KB Output is correct
20 Correct 138 ms 197196 KB Output is correct
21 Correct 127 ms 197272 KB Output is correct
22 Correct 141 ms 197240 KB Output is correct
23 Correct 138 ms 197232 KB Output is correct