제출 #89065

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
89065		igzi	Dojave (COCI17_dojave)	C++17	42 / 140	2138 ms	83252 KiB

dojave

#include <bits/stdc++.h>
#define maxN 1100005
 
using namespace std;

long long n,m,i,a[maxN],res,cnt=103;

unsigned long long x,y,b[maxN],s;
map <unsigned long long,int> p[4];

 
int main() {
    std::ios_base::sync_with_stdio(false);
    srand(time(NULL));
    if(RAND_MAX!=2147483647) cout<<-1<<endl;
    x=rand()*rand();
    x+=1-x%2;
    y=rand();
    cin>>m;
    if(m==1) {cout<<2<<endl; return 0;}
    n=pow(2,m);
    for(i=0;i<n;i++){
        cin>>a[i];
        b[a[i]]=b[n-1-a[i]]=cnt*x+y;
        cnt++;
    }
    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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 0 / 14
• Subtask 4: 14 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14