結果
問題 | No.2895 Zero XOR Subset |
ユーザー |
![]() |
提出日時 | 2024-09-20 21:26:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 169 ms / 2,000 ms |
コード長 | 1,162 bytes |
コンパイル時間 | 4,200 ms |
コンパイル使用メモリ | 255,720 KB |
最終ジャッジ日時 | 2025-02-24 09:50:07 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 35 |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 4000000000000000001LL void Gauss(vector<bitset<300>> &B){ int now = 0; rep(i,300){ int temp = -1; for(int j=now;j<B.size();j++){ if(B[j][i]){ temp = j; break; } } if(temp==-1)continue; rep(j,B.size()){ if(temp==j)continue; if(B[j][i])B[j] ^= B[temp]; } swap(B[now],B[temp]); now++; } } int main(){ int n; cin>>n; vector<long long> a(n); rep(i,n)cin>>a[i]; if(n>70)a.resize(70); vector<bitset<300>> cur; rep(i,a.size()){ bitset<300> t; rep(j,60){ if(a[i]>>j&1)t[j] = 1; } t[60+i] = 1; cur.push_back(t); Gauss(cur); bool f = true; rep(j,60){ if(cur.back()[j]){ f = false; break; } } if(f){ vector<int> ans; rep(j,100){ if(cur.back()[j+60])ans.push_back(j); } cout<<ans.size()<<endl; rep(j,ans.size()){ if(j!=0)cout<<' '; cout<<ans[j]+1; } cout<<endl; return 0; } } cout<<-1<<endl; return 0; }