이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 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; int 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++) {
while (i < k * k && xx[i] < yy[j])
i++;
if (i < k * k && xx[i] == yy[j])
i++;
else
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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |