oj.uz

Submission #1025317

# Submission time Handle Problem Language Result Execution time Memory
1025317 2024-07-16T19:50:55 Z a5a7 Secret (JOI14_secret) C++14
0 / 100
 312 ms 4452 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> v; int c;
vector<int> arr;
vector<int> mask;

void create(int left, int right, int depth){
    if (depth >= 8) return;
    if (left == right){
        return;
    }
    int mid = (left+right)/2;
    v[depth][mid] = arr[mid];
    v[depth][mid+1] = arr[mid+1];
    for (int i = mid-1; i >= left; i--) v[depth][i] = Secret(arr[i], v[depth][i+1]);
    for (int i = mid+2; i <= right; i++) v[depth][i] = Secret(v[depth][i-1], arr[i]);
    for (int i = mid+1; i <= right; i++) mask[i] ^= (1<<(c-depth-1));
    create(left, mid, depth+1);
    create(mid+1, right, depth+1);
}

void Init(int n, int a[]) {
    c = 0;
    while ((1<<c) < n) c++;
    arr = vector<int>(n);
    for (int i = 0; i < n; i++) arr[i] = a[i];
    mask = vector<int>(n, 0);
    v = vector<vector<int>>(c+2, vector<int>(n, 0));
    create(0, n-1, 0);
}

int Query(int left, int right) {
    if (left == right) return arr[left];
    if (left == (right-1)) return Secret(arr[left], arr[right]);
    int t = c-(32-(__builtin_clz(mask[left]^mask[right])));
    return Secret(v[t][left], v[t][right]);
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 2648 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 86 ms 2820 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 84 ms 2804 KB Output is correct - number of calls to Secret by Init = 3594, maximum number of calls to Secret by Query = 1
4 Incorrect 299 ms 4436 KB Wrong Answer: Query(334, 336) - expected : 757125453, actual : 536870912.
5 Incorrect 299 ms 4436 KB Wrong Answer: Query(291, 293) - expected : 410949874, actual : 536870912.
6 Incorrect 304 ms 4352 KB Wrong Answer: Query(747, 749) - expected : 244228265, actual : 536870912.
7 Correct 305 ms 4340 KB Output is correct - number of calls to Secret by Init = 7490, maximum number of calls to Secret by Query = 1
8 Correct 310 ms 4452 KB Output is correct - number of calls to Secret by Init = 7490, maximum number of calls to Secret by Query = 1
9 Correct 292 ms 4432 KB Output is correct - number of calls to Secret by Init = 7490, maximum number of calls to Secret by Query = 1
10 Correct 312 ms 4432 KB Output is correct - number of calls to Secret by Init = 7490, maximum number of calls to Secret by Query = 1