oj.uz

Submission #132580

# Submission time Handle Problem Language Result Execution time Memory
132580 2019-07-19T07:45:34 Z Adhyyan1252 Dojave (COCI17_dojave) C++11
140 / 140
 1583 ms 84056 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);
    srand(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) | rand();
        b[a[i]]=b[n-1-a[i]]=x;
    }
    s=0;
    for(i=0;i<=n;i++){
      	res += 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 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 760 KB Output is correct
2 Correct 5 ms 1016 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1664 KB Output is correct
2 Correct 8 ms 1272 KB Output is correct
3 Correct 7 ms 1176 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 5804 KB Output is correct
2 Correct 36 ms 4860 KB Output is correct
3 Correct 84 ms 8892 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 5880 KB Output is correct
2 Correct 85 ms 9080 KB Output is correct
3 Correct 230 ms 19172 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 21932 KB Output is correct
2 Correct 206 ms 17272 KB Output is correct
3 Correct 195 ms 17656 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1575 ms 83968 KB Output is correct
2 Correct 1526 ms 83580 KB Output is correct
3 Correct 889 ms 50944 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1583 ms 84056 KB Output is correct
2 Correct 1329 ms 67320 KB Output is correct
3 Correct 1142 ms 70560 KB Output is correct
4 Correct 1547 ms 83708 KB Output is correct