oj.uz

Submission #249954

# Submission time Handle Problem Language Result Execution time Memory
249954 2020-07-16T15:43:38 Z eohomegrownapps Secret (JOI14_secret) C++14
0 / 100
 500 ms 8904 KB 
#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]);
        }
    }
    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
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 2552 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 144 ms 2572 KB Output is correct - number of calls to Secret by Init = 4097, maximum number of calls to Secret by Query = 1
3 Runtime error 135 ms 4856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 498 ms 8696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 499 ms 8888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 500 ms 8824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 496 ms 8824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 498 ms 8824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 493 ms 8696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 492 ms 8904 KB Execution killed with signal 11 (could be triggered by violating memory limits)