oj.uz

Submission #1019706

# Submission time Handle Problem Language Result Execution time Memory
1019706 2024-07-11T07:57:17 Z codefox Secret (JOI14_secret) C++14
100 / 100
 327 ms 4612 KB 
#include<bits/stdc++.h>
#include "secret.h"

using namespace std;

vector<vector<int>> rright;
vector<vector<int>> lleft;

/*
int Secret(int a, int b)
{
    cout << a << " " << b << endl;
    int x;
    cin >> x;
    return x;
}
*/


void initialize(int l, int r, int A[])
{
    if (l==r) return;
    if (l==r+1) return;
    int m = (l+r)/2;
    for (int i = m+1; i < r; i++)
    {
        rright[m].push_back(Secret(rright[m].back(), A[i]));
    }
    for (int i = m-2; i >= l; i--)
    {
        lleft[m-1].push_back(Secret(A[i], lleft[m-1].back()));
    }
    initialize(l, m-1, A);
    initialize(m+1, r, A);
}

void Init(int N, int A[]) {
    rright.assign(N, vector<int>());
    lleft.assign(N, vector<int>());
    for (int i = 0; i < N; i++)
    {
        rright[i].push_back(A[i]);
        lleft[i].push_back(A[i]);
    }
    initialize(0, N, A);
}

int Query(int L, int R) {
    int ss = R-L+1;
    if (rright[L].size()>=ss)
    {
        return rright[L][ss-1];
    }
    if (lleft[R].size()>=ss)
    {
        return lleft[R][ss-1];
    }
    for (int i = L+1; i <= R; i++)
    {
        if (rright[i].size()>= R-i+1 && lleft[i-1].size()>= i-L)
        {
            return Secret(lleft[i-1][i-1-L], rright[i][R-i]);
        }
    }
    return 0;
}

/*
int main()
{
    int n, q;
    cin >> n;
    int A[n];
    for (int i = 0; i < n; i++)
    {
        cin >> A[i];
    }
    cin >> q;
    Init(n, A);
    for (int i = 0; i < q; i++)
    {
        int a, b;
        cin >> a >> b;
        cout << Query(a, b) << "\n";
    }
}
*/

Compilation message

secret.cpp: In function 'int Query(int, int)':
secret.cpp:50:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |     if (rright[L].size()>=ss)
      |         ~~~~~~~~~~~~~~~~^~~~
secret.cpp:54:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |     if (lleft[R].size()>=ss)
      |         ~~~~~~~~~~~~~~~^~~~
secret.cpp:60:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |         if (rright[i].size()>= R-i+1 && lleft[i-1].size()>= i-L)
      |             ~~~~~~~~~~~~~~~~^~~~~~~~
secret.cpp:60:58: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |         if (rright[i].size()>= R-i+1 && lleft[i-1].size()>= i-L)
      |                                         ~~~~~~~~~~~~~~~~~^~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 2580 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 90 ms 2640 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 90 ms 2636 KB Output is correct - number of calls to Secret by Init = 3100, maximum number of calls to Secret by Query = 1
4 Correct 316 ms 4436 KB Output is correct - number of calls to Secret by Init = 6988, maximum number of calls to Secret by Query = 1
5 Correct 314 ms 4436 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
6 Correct 313 ms 4612 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
7 Correct 313 ms 4592 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
8 Correct 323 ms 4436 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
9 Correct 327 ms 4608 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
10 Correct 324 ms 4540 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1