結果
問題 |
No.2895 Zero XOR Subset
|
ユーザー |
|
提出日時 | 2024-09-21 11:56:40 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 141 ms / 2,000 ms |
コード長 | 1,487 bytes |
コンパイル時間 | 1,804 ms |
コンパイル使用メモリ | 177,460 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-21 11:56:46 |
合計ジャッジ時間 | 5,875 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 35 |
コンパイルメッセージ
main.cpp: In function 'std::pair<bool, std::vector<int> > GaussianElimination(const std::vector<long long int>&, int)': main.cpp:14:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 14 | for (auto [base, ind] : basis) { | ^ main.cpp: In function 'int main()': main.cpp:49:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 49 | auto [found, ans] = GaussianElimination(a, n); | ^
ソースコード
#include<bits/stdc++.h> using namespace std; // Gaussian Elimination 関数 pair<bool, vector<int>> GaussianElimination(const vector<long long>& a, int n) { vector<pair<long long, long long>> basis; // 各成分の処理 for (int i = 0; i < n; i++) { long long value = a[i]; long long index = (1LL << i); // 既存のベースとの組み合わせ for (auto [base, ind] : basis) { if ((value ^ base) < value) { value ^= base; index ^= ind; } } // 線形従属ならば答えを出力 if (value == 0) { vector<int> ans; for (int j = 0; j <= 60; j++) { if (index & (1LL << j)) { ans.emplace_back(j + 1); } } return {true, ans}; // 解が見つかる場合 } // 新しいベースの追加 basis.emplace_back(value, index); } return {false, {}}; // 解が存在しない場合 } int main() { int n; cin >> n; vector<long long> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } // Gaussian Eliminationを使って解を求める auto [found, ans] = GaussianElimination(a, n); if (!found) { cout << -1 << endl; } else { cout << ans.size() << endl; for (int b : ans) { cout << b << " "; } cout << endl; } return 0; }