oj.uz

Submission #26412

# Submission time Handle Problem Language Result Execution time Memory
26412 2017-06-30T04:40:57 Z zscoder Secret (JOI14_secret) C++14
100 / 100
 639 ms 9996 KB 
#include "secret.h"
#include <bits/stdc++.h>

using namespace std;

int a[1010][1010];

void gen(int l, int r)
{
    if(r - l < 2)
    {
        return ;
    }
    int mid = (l+r)/2;
    for(int i = mid - 1; i >= l; i--)
    {
		//cout << i << ' ' << a[i][mid] << endl;
        if(a[i][mid] == -1)
        {
            a[i][mid] = Secret(a[i][i + 1], a[i + 1][mid]);
        }
    }
    for(int i = mid + 1; i <= r; i++)
    {
		//cout << i << ' ' << a[mid][i] << endl;
        if(a[mid][i] == -1)
        {
            a[mid][i] = Secret(a[mid][i - 1], a[i - 1][i]);
        }
    }
    gen(l, mid);
    gen(mid, r);
}
void Init(int N, int A[]) 
{
    memset(a, -1, sizeof(a));
    for(int i = 0; i < N; i++)
    {
        a[i][i + 1] = A[i];
    }
    gen(0, N);
}

int Query(int L, int R) 
{
    if(a[L][R+1] != -1) return a[L][R+1];
    for(int i = L + 1; i <= R; i++)
    {
        if(a[L][i] != -1 && a[i][R + 1] != -1)
        {
            return Secret(a[L][i], a[i][R + 1]);
        }
    }
}

Compilation message

secret.cpp: In function 'int Query(int, int)':
secret.cpp:54:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 9996 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 176 ms 9996 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 176 ms 9996 KB Output is correct - number of calls to Secret by Init = 3101, maximum number of calls to Secret by Query = 1
4 Correct 626 ms 9996 KB Output is correct - number of calls to Secret by Init = 6989, maximum number of calls to Secret by Query = 1
5 Correct 613 ms 9996 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
6 Correct 589 ms 9996 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
7 Correct 636 ms 9996 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
8 Correct 613 ms 9996 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
9 Correct 613 ms 9996 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
10 Correct 639 ms 9996 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1