oj.uz

Submission #162021

# Submission time Handle Problem Language Result Execution time Memory
162021 2019-11-05T21:07:29 Z Alexa2001 Secret (JOI14_secret) C++17
100 / 100
 628 ms 8444 KB 
#include "secret.h"
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1005;

int n;
int res[Nmax][Nmax], A[Nmax];

void divide(int st, int dr)
{
    if(dr - st <= 3)
    {
        if(res[st+1][dr-1] == -1)
            res[st+1][dr-1] = Secret(A[st+1], A[dr-1]);
        return;
    }

    int mid = (st + dr) / 2;

    divide(st, mid);
    divide(mid+1, dr);

    int i;
    for(i=mid-1; i>=st; --i)
        if(res[i][mid] == -1)
            res[i][mid] = Secret(A[i], res[i+1][mid]);

    for(i=mid+2; i<=dr; ++i)
        if(res[mid+1][i] == -1)
            res[mid+1][i] = Secret(res[mid+1][i-1], A[i]);
}

void Init(int N, int _A[])
{
    n = N;

    int i, j;
    for(i=0; i<n; ++i) A[i] = _A[i];

    for(i=0; i<n; ++i)
        for(j=i; j<n; ++j)
            res[i][j] = -1;

    for(i=0; i<n; ++i) res[i][i] = A[i];

    divide(0, n-1);
}

int answer(int st, int dr, int L, int R)
{
    if(dr - st <= 3)
    {
        if(res[L][R] != -1) return res[L][R];/// lungime 4

        /// lungime 3
        assert(R - L == 2);
        if(res[L][L+1] != -1) return Secret(res[L][L+1], A[R]);
            else
            {
                assert(res[R-1][R] != -1);
                return Secret(A[L], res[R-1][R]);
            }
    }

    int mid = (st + dr) / 2;

    if(L <= mid && mid + 1 <= R)
        return Secret(res[L][mid], res[mid+1][R]);

    if(R <= mid) return answer(st, mid, L, R);
        else return answer(mid+1, dr, L, R);
}

int Query(int L, int R)
{
    if(L == R) return A[L];
    if(L + 1 == R) return Secret(A[L], A[R]);

    /// lungime minim 3
    return answer(0, n-1, L, R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 4688 KB Output is correct - number of calls to Secret by Init = 3210, maximum number of calls to Secret by Query = 1
2 Correct 186 ms 4472 KB Output is correct - number of calls to Secret by Init = 3218, maximum number of calls to Secret by Query = 1
3 Correct 175 ms 4480 KB Output is correct - number of calls to Secret by Init = 3226, maximum number of calls to Secret by Query = 1
4 Correct 603 ms 8312 KB Output is correct - number of calls to Secret by Init = 7219, maximum number of calls to Secret by Query = 1
5 Correct 606 ms 8356 KB Output is correct - number of calls to Secret by Init = 7228, maximum number of calls to Secret by Query = 1
6 Correct 616 ms 8440 KB Output is correct - number of calls to Secret by Init = 7228, maximum number of calls to Secret by Query = 1
7 Correct 606 ms 8440 KB Output is correct - number of calls to Secret by Init = 7228, maximum number of calls to Secret by Query = 1
8 Correct 607 ms 8336 KB Output is correct - number of calls to Secret by Init = 7228, maximum number of calls to Secret by Query = 1
9 Correct 624 ms 8312 KB Output is correct - number of calls to Secret by Init = 7228, maximum number of calls to Secret by Query = 1
10 Correct 628 ms 8444 KB Output is correct - number of calls to Secret by Init = 7228, maximum number of calls to Secret by Query = 1