oj.uz

Submission #427400

# Submission time Handle Problem Language Result Execution time Memory
427400 2021-06-14T14:56:32 Z igzi Dojave (COCI17_dojave) C++17
140 / 140
 2127 ms 89476 KB 
#include <bits/stdc++.h>
#define maxN 1100005

using namespace std;

long long n,m,i,a[maxN],res;
unsigned long long x,b[maxN],s;
map <unsigned long long,int> p[4];

int main() {
    std::ios_base::sync_with_stdio(false);
    mt19937 rnd(time(NULL));
    cin>>m;
    if(m==1) {cout<<2<<endl; return 0;}
    n=pow(2,m);
    for(i=0;i<n;i++){
        cin>>a[i];
        x=rand();
      	x=(x<<32) | rnd();
        b[a[i]]=b[n-1-a[i]]=x;
    }
    s=0;
    for(i=0;i<=n;i++){
        if(p[i%4].find(s)!=p[i%4].end()) res+=p[i%4][s];
        if(p[i%4].find(s)==p[i%4].end()){
            p[i%4][s]=1;
        }
        else p[i%4][s]++;
        s=s xor b[a[i]];
    }
    cout<<(n*(n+1))/2-res<<endl;
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 3 ms 588 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 664 KB Output is correct
2 Correct 6 ms 972 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1612 KB Output is correct
2 Correct 12 ms 1300 KB Output is correct
3 Correct 6 ms 1100 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 5744 KB Output is correct
2 Correct 40 ms 4712 KB Output is correct
3 Correct 85 ms 9076 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 5760 KB Output is correct
2 Correct 130 ms 9228 KB Output is correct
3 Correct 275 ms 20296 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 22428 KB Output is correct
2 Correct 293 ms 18356 KB Output is correct
3 Correct 263 ms 18720 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1980 ms 89408 KB Output is correct
2 Correct 1941 ms 89476 KB Output is correct
3 Correct 896 ms 56612 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2025 ms 89404 KB Output is correct
2 Correct 1700 ms 73036 KB Output is correct
3 Correct 1422 ms 76464 KB Output is correct
4 Correct 2127 ms 89448 KB Output is correct