結果
問題 |
No.2895 Zero XOR Subset
|
ユーザー |
![]() |
提出日時 | 2024-09-21 13:12:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 231 ms / 2,000 ms |
コード長 | 1,423 bytes |
コンパイル時間 | 2,145 ms |
コンパイル使用メモリ | 198,268 KB |
最終ジャッジ日時 | 2025-02-24 11:14:21 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define ALL(v) v.begin(),v.end() #define dbg(x) cerr << #x << ": " << (x) << endl; int N; vector<ll>A; int main() { cin >> N; A.resize(N); for (int i = 0; i < N; ++i) cin >> A[i]; auto cp = A; vector<int> ans; vector<ll> idx(N); for (int i = 0; i < min(61,N); ++i) { idx[i] = 1LL << i; } int pos = 0; for (int j = 0; j < 60; ++j) { bool fn = false; for (int i = pos; i < N; ++i) { if (A[i] >> j & 1) { swap(A[i], A[pos]); swap(idx[i], idx[pos]); fn = true; break; } } if (fn) { for (int i = 0; i < N; ++i) { if (i != pos && (A[i] >> j & 1)) { A[i] ^= A[pos]; idx[i] ^= idx[pos]; } } ++pos; } } for (int i = 0; i < N; ++i) { if (A[i] == 0) { vector<int>ans; for (int j = 0; j <= 60; ++j) { if (idx[i] >> j & 1) { ans.push_back(j); } } cout << ans.size() << '\n'; for (int j = 0; j < ans.size(); ++j) { cout << ans[j]+1 << " \n"[j==ans.size()-1]; } return 0; } } cout << -1 << '\n'; }