제출 #1289733

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289733		hasandas	Norela (info1cup18_norela)	C++20	100 / 100	66 ms	576 KiB

norela

#include <bits/stdc++.h>

using namespace std;


int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<unsigned long long> cardMasks(n, 0ULL);

    for (int spell = 0; spell < m; ++spell) {
        int q; cin >> q;
        for (int t = 0; t < q; ++t) {
            int a; cin >> a; --a; // 0-based kart indeksi
            if (a >= 0 && a < n) cardMasks[a] |= (1ULL << spell);
        }
    }

    auto ok_mask = [&](unsigned long long mask) -> bool {
        for (int i = 0; i < n; ++i) {
            if ((__builtin_parityll(cardMasks[i] & mask)) != 1) return false;
        }
        return true;
    };

    bool found = false;
    vector<int> answer;
    for (int k = 0; k <= m && !found; ++k) {
        if (k == 0) {
            if (ok_mask(0ULL)) {
                cout << 0 << '\n' << '\n';
                return 0;
            }
            continue;
        }
        vector<int> comb(k);
        for (int i = 0; i < k; ++i) comb[i] = i;
        while (true) {
            unsigned long long mask = 0ULL;
            for (int x : comb) mask |= (1ULL << x);
            if (ok_mask(mask)) {
                found = true;
                answer = comb;
                break;
            }
            int idx = k - 1;
            while (idx >= 0 && comb[idx] == idx + m - k) --idx;
            if (idx < 0) break; // bitti
            ++comb[idx];
            for (int j = idx + 1; j < k; ++j) comb[j] = comb[j-1] + 1;
        }
    }

    if (!found) {
        cout << -1 << '\n';
        return 0;
    }

    cout << (int)answer.size() << '\n';
    for (size_t i = 0; i < answer.size(); ++i) {
        if (i) cout << ' ';
        cout << (answer[i] + 1);
    }
    cout << endl;
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25