#include <bits/stdc++.h>
#include "Annalib.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;}
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll LASTBIT(ll mask){return mask & (-mask);}
ll pop_cnt(ll mask){return __builtin_popcountll(mask);}
ll ctz(ll mask){return __builtin_ctzll(mask);}
ll clz(ll mask){return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b){a = b; return true;}
return false;
}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b){a = b; return true;}
return false;
}
template <class T>
void printArr(T& a, string separator = " ", string finish = "\n", ostream& out = cout){
for(auto i: a) out << i << separator;
out << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
struct XorBasis{
static const int N = 60;
array<ll, N> a, og;
array<ll, N> S;
XorBasis(){
for(int i = 0; i<N; ++i) a[i] = og[i] = 0;
for(int i = 0; i<N; ++i) S[i] = 0;
}
ll add(ll x){
ll y = x;
ll T = 0;
while(x > 0){
int i = logOf(x);
if (a[i] == 0) {
a[i] = x;
og[i] = y;
T ^= MASK(i);
S[i] = T;
break;
}
else {
x ^= a[i];
T ^= S[i];
}
}
return T;
}
vector<ll> getSet(ll x){
ll arr = add(x);
vector<ll> ans;
for(int i = 0; i<N; ++i) if (GETBIT(arr, i)) ans.push_back(og[i]);
sort(ALL(ans));
return ans;
}
};
// void Set(int i, int j){cout << j << ",";}
void Anna(int n, ll X, int k, int p[]){
vector<bool> banned(n);
for(int i = 0; i<k; ++i) banned[p[i]] = 1;
vector<ll> a(n);
for(int i = 0; i<n; ++i) a[i] = rngesus(0, MASK(60) - 1);
XorBasis basic;
for(int i = 0; i<n; ++i) if (!banned[i]) basic.add(a[i]);
vector<bool> tape(n);
vector<ll> S = basic.getSet(X);
for(int i = 0; i<n; ++i) if (!banned[i]) tape[i] = binary_search(ALL(S), a[i]);
for(int i = 0; i<n; ++i) Set(i, tape[i]);
}
// int main(void){
// ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// int p[] = {0};
// Anna(150, 69420, 1, p);
// return 0;
// }
#include <bits/stdc++.h>
#include "Brunolib.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;}
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll LASTBIT(ll mask){return mask & (-mask);}
ll pop_cnt(ll mask){return __builtin_popcountll(mask);}
ll ctz(ll mask){return __builtin_ctzll(mask);}
ll clz(ll mask){return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b){a = b; return true;}
return false;
}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b){a = b; return true;}
return false;
}
template <class T>
void printArr(T& a, string separator = " ", string finish = "\n", ostream& out = cout){
for(auto i: a) out << i << separator;
out << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
ll Bruno(int n, int A[]){
vector<ll> a(n);
for(int i = 0; i<n; ++i) a[i] = rngesus(0, MASK(60) - 1);
ll X = 0;
for(int i = 0; i<n; ++i) if (A[i]) X ^= a[i];
return X;
}
// int main(void){
// ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// int A[] = {0,1,1,1,1,0,1,1,1,0,1,1,1,0,0,1,0,1,0,1,1,1,1,1,0,1,0,0,1,1,1,0,0,1,0,1,0,0,0,0,1,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
// cout << Bruno(150, A) << "\n";
// return 0;
// }
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
2628 KB |
Output is correct - L* = 40 |
2 |
Correct |
45 ms |
2724 KB |
Output is correct - L* = 40 |
3 |
Correct |
47 ms |
2776 KB |
Output is correct - L* = 40 |
4 |
Correct |
44 ms |
3184 KB |
Output is correct - L* = 40 |
5 |
Correct |
47 ms |
2824 KB |
Output is correct - L* = 40 |
6 |
Correct |
46 ms |
2684 KB |
Output is correct - L* = 40 |
7 |
Correct |
50 ms |
2764 KB |
Output is correct - L* = 40 |
8 |
Correct |
46 ms |
2748 KB |
Output is correct - L* = 40 |
9 |
Correct |
46 ms |
3024 KB |
Output is correct - L* = 40 |
10 |
Correct |
45 ms |
2744 KB |
Output is correct - L* = 40 |
11 |
Correct |
45 ms |
2728 KB |
Output is correct - L* = 40 |
12 |
Correct |
45 ms |
2756 KB |
Output is correct - L* = 40 |
13 |
Correct |
45 ms |
2852 KB |
Output is correct - L* = 40 |
14 |
Correct |
45 ms |
2740 KB |
Output is correct - L* = 40 |
15 |
Correct |
46 ms |
2736 KB |
Output is correct - L* = 40 |
16 |
Correct |
44 ms |
2676 KB |
Output is correct - L* = 40 |
17 |
Correct |
44 ms |
2680 KB |
Output is correct - L* = 40 |
18 |
Correct |
44 ms |
2780 KB |
Output is correct - L* = 40 |
19 |
Correct |
45 ms |
2752 KB |
Output is correct - L* = 40 |
20 |
Correct |
46 ms |
2752 KB |
Output is correct - L* = 40 |
21 |
Correct |
45 ms |
2708 KB |
Output is correct - L* = 40 |
22 |
Correct |
45 ms |
2688 KB |
Output is correct - L* = 40 |
23 |
Correct |
44 ms |
2748 KB |
Output is correct - L* = 40 |
24 |
Correct |
44 ms |
2752 KB |
Output is correct - L* = 40 |
25 |
Correct |
44 ms |
2752 KB |
Output is correct - L* = 40 |
26 |
Correct |
45 ms |
2604 KB |
Output is correct - L* = 40 |
27 |
Correct |
44 ms |
2756 KB |
Output is correct - L* = 40 |
28 |
Correct |
44 ms |
2764 KB |
Output is correct - L* = 40 |
29 |
Correct |
45 ms |
2676 KB |
Output is correct - L* = 40 |
30 |
Correct |
44 ms |
2692 KB |
Output is correct - L* = 40 |
31 |
Correct |
45 ms |
2604 KB |
Output is correct - L* = 40 |
32 |
Correct |
45 ms |
2780 KB |
Output is correct - L* = 40 |
33 |
Correct |
45 ms |
2884 KB |
Output is correct - L* = 40 |
34 |
Correct |
45 ms |
2680 KB |
Output is correct - L* = 40 |
35 |
Correct |
45 ms |
2712 KB |
Output is correct - L* = 40 |
36 |
Correct |
45 ms |
2684 KB |
Output is correct - L* = 40 |
37 |
Correct |
45 ms |
2680 KB |
Output is correct - L* = 40 |
38 |
Correct |
45 ms |
2680 KB |
Output is correct - L* = 40 |
39 |
Correct |
47 ms |
2748 KB |
Output is correct - L* = 40 |
40 |
Correct |
48 ms |
2860 KB |
Output is correct - L* = 40 |