#include "interactive.h"
using namespace std;
typedef vector<int> vi;
const int N = 100, L = 7, M = N * L;
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int aa[N], ii[N], k;
int bb[M], ll[M], hh[M], m;
void sort(int *hh, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;
while (j < k)
if (bb[hh[j]] == bb[h])
j++;
else if (bb[hh[j]] < bb[h]) {
tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
i++, j++;
} else {
k--;
tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
}
sort(hh, l, i);
l = k;
}
}
vi guess(int n) {
vi aa(n);
aa[0] = ask(1);
m = 0;
for (int l = 0; l < L; l++) {
vi ii;
k = 0;
for (int i = 1; i < n; i++)
if ((i & 1 << l) != 0)
ii.push_back(i + 1), k++;
if (k == 0)
continue;
vi xx = get_pairwise_xor(ii); ii.push_back(1); vi yy = get_pairwise_xor(ii);
for (int i = 0, j = 0; j < (k + 1) * (k + 1); j++) {
if (j > 0 && yy[j] == yy[j - 1])
continue;
while (i < k * k && xx[i] < yy[j])
i++;
if (i == k * k || xx[i] != yy[j])
bb[m] = yy[j], ll[m] = l, m++;
}
}
for (int h = 0; h < m; h++)
hh[h] = h;
sort(hh, 0, m);
for (int h = 0, h_, i; h < m; h = h_) {
h_ = h, i = 0;
while (h_ < m && bb[hh[h_]] == bb[hh[h]])
i |= 1 << ll[hh[h_++]];
aa[i] = aa[0] ^ bb[hh[h]];
}
return aa;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
280 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
208 KB |
Output is correct |
4 |
Correct |
0 ms |
208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
336 KB |
Output is correct |
2 |
Correct |
2 ms |
336 KB |
Output is correct |
3 |
Incorrect |
1 ms |
208 KB |
Output is not correct |
4 |
Halted |
0 ms |
0 KB |
- |