제출 #950941

#제출 시각아이디문제언어결과실행 시간메모리
950941qwe1rt1yuiop1Toxic Gene (NOI23_toxic)C++17
10.15 / 100
10 ms604 KiB
#include "toxic.h" using namespace std; #include <bits/stdc++.h> #define sz(x) (int)x.size() vector<int> v; string ans; int n0; void ac(int x, char c) { assert(ans[x] == '0'); // x = n0 - x + 1; answer_type(x, c); // x = n0 - x + 1; ans[x] = c; } int qry() { // for (int &i : v) // i = n0 - i + 1; int ret = query_sample(v); // for (int &i : v) // i = n0 - i + 1; return ret; } int qry1(int l, int r) { v.clear(); for (int i = l; i <= r; ++i) v.emplace_back(i); return qry(); } void qry2() { int cnt = sz(v) - 1; for (int i = 0; i < cnt; ++i) for (int j = 0; j < ((1 << i) - 1); ++j) v.emplace_back(v[i]); int tmp = sz(v); assert(tmp == (tmp & (-tmp))); int ret = qry(); // --ret; for (int i = 0; i < cnt; ++i) if (ret >> i & 1) ac(v[i], 'S'); else ac(v[i], 'R'); } void determine_type(int n) { n0 = n; ans.assign(n + 1, '0'); vector<int> t; t.emplace_back(0); while (1) { int l = t.back() + 1, r = n; if (l > r || qry1(l, r) == r - l + 1) break; while (l < r) { int mid = (l + r) >> 1; if (qry1(l, mid) == mid - l + 1) l = mid + 1; else r = mid; } t.emplace_back(l); ac(l, 'T'); } /* for (int i = 1; i <= n; ++i) if (ans[i] == '0') { v.clear(); v.emplace_back(t.back()); v.emplace_back(i); if (qry() == 1) ac(i, 'S'); else ac(i, 'R'); } */ vector<int> r; for (int i = 1; i <= n; ++i) if (ans[i] == '0') r.emplace_back(i); while (!r.empty()) { v.clear(); while (!r.empty() && sz(v) < 8) v.emplace_back(r.back()), r.pop_back(); v.emplace_back(t.back()); qry2(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...