Submission #249958

#	Time	Username	Problem	Language	Result	Execution time	Memory
249958		eohomegrownapps	Secret (JOI14_secret)	C++14	100 / 100	522 ms	4560 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

int lptr[10][1000];
int rptr[10][1000];
int table[10][1000];

int n;

int findValue(int l, int r, int p){
    if (l==r){
        return table[0][l];
    }
    for (int i = p; i>=0; i--){
        if (lptr[i][l]==-1||rptr[i][r]==-1){continue;}
        if (lptr[i][l]+rptr[i][r]==(r-l+1)){
            return Secret(table[i][l],table[i][r]);
        }
    }
    return -1;
    //assert(1==0);
}
int maxp = 0;

void Init(int N, int A[]) {
    n=N;
    for (int i = 0; i<n; i++){
        table[0][i]=A[i];
        if (i%2==0){
            lptr[0][i]=1;
            rptr[0][i]=-1;
        } else {
            lptr[0][i]=-1;
            rptr[0][i]=1;
        }
    }
    for (int p = 1; (1<<p)<=n; p++){
        int len = 1<<p;
        int cnt = 1<<p;
        bool leftp = true;
        maxp=max(maxp,p);
        for (int i = 0; i<n; i++){
            if (leftp&&cnt==0){
                cnt=1;
                leftp=false;
            } else if ((!leftp)&&cnt==len+1){
                cnt=len;
                leftp=true;
            }
            if (leftp){
                lptr[p][i]=cnt;
                rptr[p][i]=-1;
                table[p][i]=findValue(i,i+cnt-1,p-1);
                cnt--;
            } else {
                lptr[p][i]=-1;
                rptr[p][i]=cnt;
                table[p][i]=findValue(i-cnt+1,i,p-1);
                cnt++;
            }
        }
    }
}

int Query(int L, int R) {
    return findValue(L,R,maxp);
}

• Subtask 1: 100 / 100