oj.uz

Submission #55342

# Submission time Handle Problem Language Result Execution time Memory
55342 2018-07-07T04:57:51 Z red1108 Secret (JOI14_secret) C++17
0 / 100
 671 ms 4804 KB 
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include "secret.h"
using namespace std;
int si=1,h=1;
int dp[20][2000];
int input[2000];
int cnt=0;
int secret(int x, int y)
{
    if(x==-1) return y;
    else if(y==-1) return x;
    return Secret(x, y);
}
void fillup(int st,int l, int r)
{
    int mid, i;
    if(st>=9) return ;
    mid=(r+l-1)/2;
    for(i=mid;i>=l;i--)
    {
        if(i==mid) {dp[st][i]=input[i];continue;}
        dp[st][i]=secret(input[i],dp[st][i+1]);
    }
    mid=(r+l+1)/2;
    for(i=mid;i<=r;i++)
    {
        if(i==mid) {dp[st][i]=input[i];continue;}
        dp[st][i]=secret(dp[st][i-1],input[i]);
    }
    fillup(st+1, l, (l+r)/2);
    fillup(st+1, (l+r)/2+1, r);
}
void Init(int N, int A[])
{
    int i,j;
    while(si<N) {si*=2;h++;}
    for(i=N;i>=1;i--)
    {
        input[i]=A[i-1];
    }
    for(i=N+1;i<=si;i++) input[i]=-1;
    for(i=1;i<=h+1;i++)
    {
        for(j=1;j<=N*2;j++)
        {
            dp[i][j]=-1;
        }
    }
    fillup(1,1,si);
}
int query(int x,int st,int l, int r, int s, int e)
{
    int mid;
    mid=(l+r)/2;
    if(l+r<s*2) return query(x*2+1,st+1,(l+r)/2+1, r, s, e);
    else if(l+r>e*2) return query(x*2,st+1, l, (l+r)/2, s, e);
    else
    {
        return secret(dp[st][s],dp[st][e]);
    }
}
int Query(int L, int R)
{
    L++;
    R++;
    if(L+1==R) return secret(input[L],input[R]);
    else if(L==R) return input[L];
    return query(1,1,1,si,L, R);
}

Compilation message

secret.cpp: In function 'int query(int, int, int, int, int, int)':
secret.cpp:55:9: warning: variable 'mid' set but not used [-Wunused-but-set-variable]
     int mid;
         ^~~

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 181 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 183 ms 2560 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Incorrect 157 ms 2644 KB Wrong Answer: Query(501, 503) - expected : 479731268, actual : -1.
4 Incorrect 600 ms 4792 KB Wrong Answer: Query(768, 771) - expected : 927845157, actual : -1.
5 Incorrect 600 ms 4792 KB Wrong Answer: Query(84, 87) - expected : 811856482, actual : -1.
6 Incorrect 571 ms 4792 KB Wrong Answer: Query(628, 630) - expected : 272199500, actual : -1.
7 Correct 632 ms 4792 KB Output is correct - number of calls to Secret by Init = 7500, maximum number of calls to Secret by Query = 1
8 Correct 671 ms 4792 KB Output is correct - number of calls to Secret by Init = 7500, maximum number of calls to Secret by Query = 1
9 Correct 586 ms 4792 KB Output is correct - number of calls to Secret by Init = 7500, maximum number of calls to Secret by Query = 1
10 Correct 639 ms 4804 KB Output is correct - number of calls to Secret by Init = 7500, maximum number of calls to Secret by Query = 1