oj.uz

답안 #89092

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
89092 2018-12-10T09:47:24 Z igzi Dojave (COCI17_dojave) C++17
140 / 140
 2082 ms 82872 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++){
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 584 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 584 KB Output is correct
2 Correct 2 ms 584 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 804 KB Output is correct
2 Correct 4 ms 828 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 956 KB Output is correct
2 Correct 7 ms 1212 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 1852 KB Output is correct
2 Correct 9 ms 1852 KB Output is correct
3 Correct 9 ms 1852 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 5708 KB Output is correct
2 Correct 62 ms 5708 KB Output is correct
3 Correct 125 ms 8796 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 8796 KB Output is correct
2 Correct 138 ms 8796 KB Output is correct
3 Correct 304 ms 18860 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 398 ms 21080 KB Output is correct
2 Correct 327 ms 21080 KB Output is correct
3 Correct 282 ms 21080 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2082 ms 82764 KB Output is correct
2 Correct 1952 ms 82764 KB Output is correct
3 Correct 888 ms 82764 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2056 ms 82764 KB Output is correct
2 Correct 1565 ms 82764 KB Output is correct
3 Correct 1401 ms 82764 KB Output is correct
4 Correct 1941 ms 82872 KB Output is correct