#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]);
}
# |
결과 |
실행 시간 |
메모리 |
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 |