제출 #770058

#제출 시각아이디문제언어결과실행 시간메모리
770058rainboyXoractive (IZhO19_xoractive)C++17
100 / 100
2 ms348 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...