oj.uz

Submission #77616

# Submission time Handle Problem Language Result Execution time Memory
77616 2018-09-29T05:18:57 Z ccinv Dojave (COCI17_dojave) C++11
70 / 140
 1454 ms 62384 KB 
#include <bits/stdc++.h>
using namespace std;

#define oo 0x3f3f3f3f
#define mp make_pair
#define fi first
#define se second
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define FO(i,a,b) for (int i=(a);i<=(b);++i)
#define FD(i,a,b) for (int i=(a);i>=(b);--i)
#define FE(i,G,x) for(int i=(G).h[x];~i;i=(G).v[i].nxt)
typedef long long LL;
typedef pair<int, int> PII;

template <class T> inline bool chkmin(T& x, T y) { return x > y ? x = y, true : false; }
template <class T> inline bool chkmax(T& x, T y) { return x < y ? x = y, true : false; }

inline LL read(void) {
    LL x, f = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
    for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
    return x * f;
}

typedef int U;
#define N ((1<<20)+5)

LL ans; U f[N];
int m,s,p[N],a[N];
map<U,int> M[4];

mt19937 g1(19260817);

int main(void) {
    m=read();s=(1<<m)-1;
    FO(i,0,s) a[i]=read(),p[a[i]]=i;
    FO(i,0,s/2){ f[p[i]]=g1();f[p[s^i]]=f[p[i]]; }

    M[3][0]=1;
    FO(i,0,s){
        f[i]^=f[i-1];
        ans+=M[i%4][f[i]];M[i%4][f[i]]++;
    }
    printf("%lld\n",1ll*(s+1)*(s+2)/2-ans);
    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

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 576 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 792 KB Output is correct
2 Correct 4 ms 836 KB Output is correct

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1536 KB Output is correct
2 Correct 7 ms 1536 KB Output is correct
3 Correct 6 ms 1536 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 4512 KB Output is correct
2 Correct 38 ms 4512 KB Output is correct
3 Correct 81 ms 6808 KB Output is correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 6808 KB Output is correct
2 Incorrect 81 ms 6816 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 275 ms 15972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1454 ms 62356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1422 ms 62384 KB Output isn't correct
2 Halted 0 ms 0 KB -