Submission #1289675

#TimeUsernameProblemLanguageResultExecution timeMemory
1289675ragzurtNorela (info1cup18_norela)C++20
75 / 100
983 ms580 KiB
#pragma GCC optimize ("O3,unroll-loops")
//#pragma GCC target ("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
//#define int long long
using namespace std;

vector<vector<char>> sp; // boyumu aşan soruya giriştim ya 100le çıkıp sonlarda takılcaz ya da soruyu yapıp top 5 yapcaz (kesin debug atamıcam)
vector<char> cur, tgt;
vector<int> cmb;
bool ok;

void dfs(int st, int need, int n, int m){ // 800 ms ne oha
    if(ok) return;
    if(need==0){
        for(int i=0; i<n; i++) if(cur[i]==0) return;
        cout<<cmb.size()<<"\n";
        for(size_t i=0; i<cmb.size(); i++){ if(i) cout<<" "; cout<<cmb[i]; } cout<<"\n";
        ok=true; return;
    }
    for(int i=st; i<=m-need; i++){
        for(int p=0; p<n; p++) cur[p]^=sp[i][p];
        cmb.push_back(i+1);
        dfs(i+1, need-1, n, m);
        if(ok) return;
        cmb.pop_back();
        for(int p=0; p<n; p++) cur[p]^=sp[i][p];
    }
}

int32_t main(){ // galiba debug attım (caresizim, yardım gönderin)
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n, m; cin>>n>>m;
    sp.assign(m, vector<char>(n, 0));
    cur.assign(n, 0);
    tgt.assign(n, 1);
    for(int i=0; i<m; i++){
        int q; cin>>q;
        for(int j=0; j<q; j++){
            int v; cin>>v; v--;
            sp[i][v]=1;
        }
    }
    cmb.clear();
    ok=false;
    for(int t=1; t<=m && !ok; t++) dfs(0, t, n, m);
    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...