제출 #817083

#제출 시각아이디문제언어결과실행 시간메모리
817083rainboyAncient Machine 2 (JOI23_ancient2)C++17
100 / 100
37 ms724 KiB
/* upsolved with help from GusterGoose27 */ #include "ancient2.h" #include <cstring> #include <vector> using namespace std; typedef unsigned long long ull; typedef vector<int> vi; const int N = 1000, M = 102, L = 64, K = (N + L - 1) / L; ull vvv[N][K]; int ww[N]; int add(ull *vv) { int w = 0; for (int i = 0; i < N; i++) if ((vv[i / L] & 1ULL << i % L) != 0) { if ((vvv[i][i / L] & 1ULL << i % L) != 0) { for (int h = i / L; h < K; h++) vv[h] ^= vvv[i][h]; w ^= ww[i]; } else { for (int h = i / L; h < K; h++) vvv[i][h] = vv[h]; ww[i] = w; return i; } } return -1; } string Solve(int n) { string cc(N, '0'); ull vv[K]; int rank = 0; for (int i = 0; i + 3 <= M; i++) { memset(vv, 0, K * sizeof *vv), vv[i / L] |= 1ULL << i % L; add(vv), rank++; int m = i + 3; vi aa(m), bb(m); for (int s = 0; s < i; s++) aa[s] = bb[s] = s + 1; aa[i] = i + 1, bb[i] = i + 2; aa[i + 1] = bb[i + 1] = i + 1; aa[i + 2] = bb[i + 2] = i + 2; if (Query(m, aa, bb) != i + 1) ww[i] ^= 1; } for (int i = N - 1; N - i + 1 <= M; i--) { memset(vv, 0, K * sizeof *vv), vv[i / L] |= 1ULL << i % L; add(vv), rank++; cc[i] = '0'; int m = N - i + 1; vi aa(m), bb(m); int f = -1; for (int s = 0; s + 1 < m; s++) { if (cc[i + s] == '0') aa[s] = s + 1, bb[s] = f == -1 ? 0 : bb[f]; else aa[s] = f == -1 ? 0 : aa[f], bb[s] = s + 1; f = f == -1 ? 0 : (cc[i + s] == '0' ? aa[f] : bb[f]); } aa[m - 1] = aa[f], bb[m - 1] = bb[f]; if (Query(m, aa, bb) != m - 1) ww[i] ^= 1, cc[i] = '1'; } for (int c = 1; c * 2 <= M; c++) { int m = c * 2; vi aa(m), bb(m); for (int r = 0; r < c; r++) { memset(vv, 0, K * sizeof *vv); for (int i = 0; i < N; i++) if (i % c == r) vv[i / L] |= 1ULL << i % L; int i = add(vv); if (i != -1) { rank++; for (int s = 0; s < c; s++) { aa[s] = bb[s] = (s + 1) % c; aa[c + s] = bb[c + s] = c + (s + 1) % c; } bb[r] = c + (r + 1) % c; bb[c + r] = (r + 1) % c; if (Query(m, aa, bb) >= c) ww[i] ^= 1; } } } if (rank != N) return ":("; for (int i = N - 1; i >= 0; i--) { for (int j = i + 1; j < N; j++) if ((vvv[i][j / L] & 1ULL << j % L) != 0) ww[i] ^= ww[j]; cc[i] = ww[i] + '0'; } return cc; }
#Verdict Execution timeMemoryGrader output
Fetching results...