# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
236222 |
2020-05-31T16:29:39 Z |
VEGAnn |
Dojave (COCI17_dojave) |
C++14 |
|
953 ms |
45772 KB |
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define PB push_back
#define MP make_pair
#define all(x) x.begin(),x.end()
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N = (1 << 20);
const int oo = 2e9;
vector<pair<ull, int> > vc;
ull vl[N], ans = 0;
int m, n, a[N], kol[N];
mt19937_64 rnd(chrono::system_clock().now().time_since_epoch().count());
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
freopen("in.txt","r",stdin);
#endif // _LOCAL
cin >> m;
n = (1 << m);
if (m == 1){
cout << 2;
return 0;
}
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n; i++){
int obr = ((n - 1) ^ i);
if (obr < i) continue;
vl[i] = rnd();
vl[obr] = ull(0) - vl[i];
}
vc.PB(MP(0, 0));
ull sum = 0;
int xr = 0;
for (int i = 0; i < n; i++){
sum += vl[a[i]];
xr ^= a[i];
vc.PB(MP(sum, xr));
}
sort(all(vc));
vc.resize(unique(all(vc)) - vc.begin());
kol[0]++;
sum = 0;
xr = 0;
for (int i = 0; i < n; i++){
sum += vl[a[i]];
xr ^= a[i];
int id = lower_bound(all(vc), MP(sum, xr)) - vc.begin();
ans += kol[id];
kol[id]++;
}
cout << ull(n) * (ull(n) + 1) / 2 - ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
640 KB |
Output is correct |
2 |
Correct |
6 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
896 KB |
Output is correct |
2 |
Correct |
7 ms |
872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
1280 KB |
Output is correct |
2 |
Correct |
9 ms |
1280 KB |
Output is correct |
3 |
Correct |
9 ms |
1152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
3320 KB |
Output is correct |
2 |
Correct |
31 ms |
3320 KB |
Output is correct |
3 |
Correct |
53 ms |
6132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
3320 KB |
Output is correct |
2 |
Correct |
62 ms |
6124 KB |
Output is correct |
3 |
Correct |
122 ms |
11752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
153 ms |
11880 KB |
Output is correct |
2 |
Correct |
130 ms |
11880 KB |
Output is correct |
3 |
Correct |
129 ms |
11752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
953 ms |
45632 KB |
Output is correct |
2 |
Correct |
795 ms |
45632 KB |
Output is correct |
3 |
Correct |
505 ms |
45772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
870 ms |
45648 KB |
Output is correct |
2 |
Correct |
686 ms |
45624 KB |
Output is correct |
3 |
Correct |
586 ms |
45648 KB |
Output is correct |
4 |
Correct |
810 ms |
45652 KB |
Output is correct |