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 | 6 ms | 4 MB |
g++ | 20_random_large01.in | AC | 17 ms | 4 MB |
g++ | 20_random_large02.in | AC | 9 ms | 4 MB |
g++ | 20_random_large03.in | AC | 15 ms | 4 MB |
g++ | 20_random_large04.in | AC | 12 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 | 14 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 | 19 ms | 4 MB |
g++ | 30_corner01.in | AC | 7 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 | 21 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 | 6 ms | 4 MB |
g++ | 40_random_small05.in | AC | 6 ms | 4 MB |
g++ | 50_random_large01.in | AC | 15 ms | 4 MB |
g++ | 50_random_large02.in | AC | 20 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 | 21 ms | 4 MB |
clang++ | 00_sample01.in | AC | 7 ms | 4 MB |
clang++ | 00_sample02.in | AC | 6 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 | 6 ms | 4 MB |
clang++ | 10_random_small05.in | AC | 7 ms | 4 MB |
clang++ | 20_random_large01.in | AC | 17 ms | 4 MB |
clang++ | 20_random_large02.in | AC | 9 ms | 4 MB |
clang++ | 20_random_large03.in | AC | 14 ms | 4 MB |
clang++ | 20_random_large04.in | AC | 12 ms | 4 MB |
clang++ | 20_random_large05.in | AC | 19 ms | 4 MB |
clang++ | 20_random_large06.in | AC | 20 ms | 4 MB |
clang++ | 20_random_large07.in | AC | 14 ms | 4 MB |
clang++ | 20_random_large08.in | AC | 21 ms | 4 MB |
clang++ | 20_random_large09.in | AC | 18 ms | 4 MB |
clang++ | 20_random_large10.in | AC | 20 ms | 4 MB |
clang++ | 30_corner01.in | AC | 7 ms | 4 MB |
clang++ | 30_corner02.in | AC | 6 ms | 4 MB |
clang++ | 30_corner03.in | AC | 9 ms | 4 MB |
clang++ | 30_corner04.in | AC | 21 ms | 4 MB |
clang++ | 30_corner05.in | AC | 21 ms | 4 MB |
clang++ | 40_random_small01.in | AC | 6 ms | 4 MB |
clang++ | 40_random_small02.in | AC | 7 ms | 4 MB |
clang++ | 40_random_small03.in | AC | 6 ms | 4 MB |
clang++ | 40_random_small04.in | AC | 6 ms | 4 MB |
clang++ | 40_random_small05.in | AC | 7 ms | 4 MB |
clang++ | 50_random_large01.in | AC | 15 ms | 4 MB |
clang++ | 50_random_large02.in | AC | 19 ms | 4 MB |
clang++ | 50_random_large03.in | AC | 17 ms | 4 MB |
clang++ | 50_random_large04.in | AC | 16 ms | 4 MB |
clang++ | 50_random_large05.in | AC | 18 ms | 4 MB |
clang++ | system_test1.txt | AC | 21 ms | 4 MB |
clang++ | system_test2.txt | AC | 21 ms | 4 MB |
clang++ | system_test3.txt | AC | 21 ms | 4 MB |
clang++ | system_test4.txt | AC | 21 ms | 4 MB |