#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
/*int Secret(int a, int b) {
return a ^ b;
}*/
const int mxN = 1000, mxK = 10;
int n, a[mxN];
int tl[mxN][mxK], tr[mxN][mxK];
void Init(int N, int A[]) {
n = N;
for (int i = 0; i < n; ++i) {
a[i] = A[i];
}
for (int j = 1; (1 << j) <= n; ++j) {
int mask = (1 << j) - 1;
int temp;
for (int i = 0; i < n; ++i) {
if (i % (1 << (j + 1)) < (1 << j)) {
continue;
}
temp = ((i & mask) == 0) ? a[i] : Secret(temp, a[i]);
tr[i][j] = temp;
}
for (int i = n - 1; ~i; --i) {
if (i % (1 << (j + 1)) >= (1 << j)) {
continue;
}
temp = ((i & mask) == mask || i == n - 1) ? a[i] : Secret(a[i], temp);
tl[i][j] = temp;
}
}
}
int Query(int L, int R) {
if (L == R) return a[L];
if (R == L + 1) return Secret(a[L], a[R]);
int x = 31 - __builtin_clz(L ^ R);
return Secret(tl[L][x], tr[R][x]);
}
/*int Brute(int L, int R) {
int ans = a[L];
for (int i = L + 1; i <= R; ++i) {
ans = Secret(ans, a[i]);
}
return ans;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int a[100];
for (int i = 0; i < 100; ++i) {
a[i] = rng() % 1000 + 1;
}
Init(100, a);
//for (int i = 0; i < 3; ++i) for (int j = i; j < 3; ++j) cout << i << " " << j << " " << Query(i, j) << "\n";
for (int i = 0; i < 100; ++i) {
for (int j = i; j < 100; ++j) {
if (Brute(i, j) != Query(i, j)) {
cout << i << " " << j << "\n";
return 0;
}
}
}
return 0;
}*/
Compilation message
secret.cpp: In function 'void Init(int, int*)':
secret.cpp:25:44: warning: 'temp' may be used uninitialized in this function [-Wmaybe-uninitialized]
25 | temp = ((i & mask) == 0) ? a[i] : Secret(temp, a[i]);
| ~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
143 ms |
2424 KB |
Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1 |
| 2 |
Correct |
144 ms |
2424 KB |
Output is correct - number of calls to Secret by Init = 4097, maximum number of calls to Secret by Query = 1 |
| 3 |
Correct |
147 ms |
2424 KB |
Output is correct - number of calls to Secret by Init = 4097, maximum number of calls to Secret by Query = 1 |
| 4 |
Correct |
503 ms |
4472 KB |
Output is correct - number of calls to Secret by Init = 7991, maximum number of calls to Secret by Query = 1 |
| 5 |
Correct |
506 ms |
4472 KB |
Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1 |
| 6 |
Correct |
507 ms |
4344 KB |
Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1 |
| 7 |
Correct |
510 ms |
4648 KB |
Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1 |
| 8 |
Correct |
511 ms |
4472 KB |
Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1 |
| 9 |
Correct |
505 ms |
4344 KB |
Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1 |
| 10 |
Correct |
504 ms |
4344 KB |
Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1 |
