This documentation is automatically generated by online-judge-tools/verification-helper
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/184
#include "../../template/template.hpp"
#include "../../math/matrix/binary-basis.hpp"
int main() {
int N;
cin >> N;
BinaryBasis< int64 > bb;
for(int i = 0; i < N; i++) {
int64 x;
cin >> x;
bb.add(x);
}
cout << (1LL << bb.size()) << "\n";
}
#line 1 "test/verify/yukicoder-184.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/184
#line 1 "template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;
struct IoSetup {
IoSetup() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
cerr << fixed << setprecision(10);
}
} iosetup;
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
os << p.first << " " << p.second;
return os;
}
template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
is >> p.first >> p.second;
return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
for (int i = 0; i < (int)v.size(); i++) {
os << v[i] << (i + 1 != v.size() ? " " : "");
}
return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
for (T &in : v) is >> in;
return is;
}
template <typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {
return a < b && (a = b, true);
}
template <typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {
return a > b && (a = b, true);
}
template <typename T = int64>
vector<T> make_v(size_t a) {
return vector<T>(a);
}
template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type fill_v(T &t, const V &v) {
t = v;
}
template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type fill_v(T &t, const V &v) {
for (auto &e : t) fill_v(e, v);
}
template <typename F>
struct FixPoint : F {
explicit FixPoint(F &&f) : F(forward<F>(f)) {}
template <typename... Args>
decltype(auto) operator()(Args &&...args) const {
return F::operator()(*this, forward<Args>(args)...);
}
};
template <typename F>
inline decltype(auto) MFP(F &&f) {
return FixPoint<F>{forward<F>(f)};
}
#line 4 "test/verify/yukicoder-184.test.cpp"
#line 1 "math/matrix/binary-basis.hpp"
template <typename T>
struct BinaryBasis {
vector<T> basis;
bool update;
BinaryBasis() : update(false) {}
bool add(T bit) {
for (auto &p : basis) {
bit = min(bit, bit ^ p);
}
if (bit) {
basis.emplace_back(bit);
return update = true;
} else {
return false;
}
}
bool check(T bit) const {
for (auto &p : basis) {
bit = min(bit, bit ^ p);
}
return bit == 0;
}
void normalize() {
sweep();
for (int i = (int)basis.size() - 1; i >= 0; i--) {
for (int j = i - 1; j >= 0; j--) chmin(basis[i], basis[i] ^ basis[j]);
}
}
void sweep() {
if (exchange(update, false)) {
sort(begin(basis), end(basis));
}
}
bool operator==(BinaryBasis<T> &a) {
normalize(), a.normalize();
return basis == a.basis;
}
T get_kth(int64_t k) { /* 0-indexed */
if ((1LL << basis.size()) <= k) {
return -1;
}
T ret = T();
sweep();
for (int i = (int)basis.size() - 1; i >= 0; i--) {
if (k < (1LL << i)) {
ret = min(ret, ret ^ basis[i]);
} else {
k -= 1LL << i;
ret = max(ret, ret ^ basis[i]);
}
}
return ret;
}
size_t size() const { return basis.size(); }
};
#line 6 "test/verify/yukicoder-184.test.cpp"
int main() {
int N;
cin >> N;
BinaryBasis< int64 > bb;
for(int i = 0; i < N; i++) {
int64 x;
cin >> x;
bb.add(x);
}
cout << (1LL << bb.size()) << "\n";
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | 00_sample01.in | AC | 7 ms | 4 MB |
g++ | 00_sample02.in | AC | 7 ms | 4 MB |
g++ | 00_sample03.in | AC | 7 ms | 4 MB |
g++ | 10_random_small01.in | AC | 7 ms | 4 MB |
g++ | 10_random_small02.in | AC | 7 ms | 4 MB |
g++ | 10_random_small03.in | AC | 7 ms | 4 MB |
g++ | 10_random_small04.in | AC | 7 ms | 4 MB |
g++ | 10_random_small05.in | AC | 7 ms | 4 MB |
g++ | 20_random_large01.in | AC | 18 ms | 4 MB |
g++ | 20_random_large02.in | AC | 10 ms | 4 MB |
g++ | 20_random_large03.in | AC | 16 ms | 4 MB |
g++ | 20_random_large04.in | AC | 13 ms | 4 MB |
g++ | 20_random_large05.in | AC | 19 ms | 4 MB |
g++ | 20_random_large06.in | AC | 20 ms | 4 MB |
g++ | 20_random_large07.in | AC | 16 ms | 4 MB |
g++ | 20_random_large08.in | AC | 21 ms | 4 MB |
g++ | 20_random_large09.in | AC | 19 ms | 4 MB |
g++ | 20_random_large10.in | AC | 20 ms | 4 MB |
g++ | 30_corner01.in | AC | 8 ms | 4 MB |
g++ | 30_corner02.in | AC | 7 ms | 4 MB |
g++ | 30_corner03.in | AC | 10 ms | 4 MB |
g++ | 30_corner04.in | AC | 21 ms | 4 MB |
g++ | 30_corner05.in | AC | 22 ms | 4 MB |
g++ | 40_random_small01.in | AC | 7 ms | 4 MB |
g++ | 40_random_small02.in | AC | 7 ms | 4 MB |
g++ | 40_random_small03.in | AC | 7 ms | 4 MB |
g++ | 40_random_small04.in | AC | 7 ms | 4 MB |
g++ | 40_random_small05.in | AC | 7 ms | 4 MB |
g++ | 50_random_large01.in | AC | 15 ms | 4 MB |
g++ | 50_random_large02.in | AC | 19 ms | 4 MB |
g++ | 50_random_large03.in | AC | 18 ms | 4 MB |
g++ | 50_random_large04.in | AC | 16 ms | 4 MB |
g++ | 50_random_large05.in | AC | 18 ms | 4 MB |
g++ | system_test1.txt | AC | 21 ms | 4 MB |
g++ | system_test2.txt | AC | 21 ms | 4 MB |
g++ | system_test3.txt | AC | 22 ms | 4 MB |
g++ | system_test4.txt | AC | 22 ms | 4 MB |
clang++ | 00_sample01.in | AC | 7 ms | 4 MB |
clang++ | 00_sample02.in | AC | 7 ms | 4 MB |
clang++ | 00_sample03.in | AC | 7 ms | 4 MB |
clang++ | 10_random_small01.in | AC | 7 ms | 4 MB |
clang++ | 10_random_small02.in | AC | 7 ms | 4 MB |
clang++ | 10_random_small03.in | AC | 7 ms | 4 MB |
clang++ | 10_random_small04.in | AC | 7 ms | 4 MB |
clang++ | 10_random_small05.in | AC | 7 ms | 4 MB |
clang++ | 20_random_large01.in | AC | 18 ms | 4 MB |
clang++ | 20_random_large02.in | AC | 10 ms | 4 MB |
clang++ | 20_random_large03.in | AC | 15 ms | 4 MB |
clang++ | 20_random_large04.in | AC | 14 ms | 4 MB |
clang++ | 20_random_large05.in | AC | 20 ms | 4 MB |
clang++ | 20_random_large06.in | AC | 21 ms | 4 MB |
clang++ | 20_random_large07.in | AC | 15 ms | 4 MB |
clang++ | 20_random_large08.in | AC | 22 ms | 4 MB |
clang++ | 20_random_large09.in | AC | 20 ms | 4 MB |
clang++ | 20_random_large10.in | AC | 21 ms | 4 MB |
clang++ | 30_corner01.in | AC | 8 ms | 4 MB |
clang++ | 30_corner02.in | AC | 7 ms | 4 MB |
clang++ | 30_corner03.in | AC | 10 ms | 4 MB |
clang++ | 30_corner04.in | AC | 22 ms | 4 MB |
clang++ | 30_corner05.in | AC | 23 ms | 4 MB |
clang++ | 40_random_small01.in | AC | 8 ms | 4 MB |
clang++ | 40_random_small02.in | AC | 7 ms | 4 MB |
clang++ | 40_random_small03.in | AC | 7 ms | 4 MB |
clang++ | 40_random_small04.in | AC | 7 ms | 4 MB |
clang++ | 40_random_small05.in | AC | 7 ms | 4 MB |
clang++ | 50_random_large01.in | AC | 16 ms | 4 MB |
clang++ | 50_random_large02.in | AC | 20 ms | 4 MB |
clang++ | 50_random_large03.in | AC | 18 ms | 4 MB |
clang++ | 50_random_large04.in | AC | 17 ms | 4 MB |
clang++ | 50_random_large05.in | AC | 19 ms | 4 MB |
clang++ | system_test1.txt | AC | 22 ms | 4 MB |
clang++ | system_test2.txt | AC | 22 ms | 4 MB |
clang++ | system_test3.txt | AC | 22 ms | 4 MB |
clang++ | system_test4.txt | AC | 22 ms | 4 MB |