Submission #1289621

#TimeUsernameProblemLanguageResultExecution timeMemory
1289621amodi_ssNorela (info1cup18_norela)C++20
0 / 100
1 ms332 KiB
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 60;  // n kart
const int MAXM = 60;  // m büyü

int n, m;
bitset<MAXM> A[MAXN];  // Kartlar x Büyüler matrisi
bitset<MAXM> solution; // Çözüm vektörü
int B[MAXN];           // Hedef kart durumu (1 face up)

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

    cin >> n >> m;
    
    for (int i = 0; i < n; i++) B[i] = 1; // Tüm kartlar face up

    for (int j = 0; j < m; j++) {
        int q; cin >> q;
        for (int k = 0; k < q; k++) {
            int idx; cin >> idx;
            idx--; // 0-indexed
            A[idx][j] = 1;
        }
    }

    // Gauss eliminasyonu mod 2
    int row = 0;
    vector<int> where(m, -1); // Hangi sütun hangi pivot
    for (int col = 0; col < m && row < n; col++) {
        int sel = -1;
        for (int i = row; i < n; i++)
            if (A[i][col]) { sel = i; break; }
        if (sel == -1) continue;

        swap(A[sel], A[row]);
        swap(B[sel], B[row]);
        where[col] = row;

        for (int i = 0; i < n; i++) {
            if (i != row && A[i][col]) {
                A[i] ^= A[row];
                B[i] ^= B[row];
            }
        }
        row++;
    }

    // Çözümü bul
    solution.reset();
    for (int i = 0; i < m; i++) {
        if (where[i] != -1)
            solution[i] = B[where[i]];
    }

    // Sonuç
    vector<int> used;
    for (int i = 0; i < m; i++)
        if (solution[i]) used.push_back(i+1);

    cout << used.size() << "\n";
    for (int i = 0; i < (int)used.size(); i++) {
        if (i) cout << " ";
        cout << used[i];
    }
    cout << "\n";

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...