Submission #950994

#TimeUsernameProblemLanguageResultExecution timeMemory
950994qwe1rt1yuiop1Toxic Gene (NOI23_toxic)C++17
25.29 / 100
11 ms536 KiB
#include "toxic.h" using namespace std; #include <bits/stdc++.h> #define sz(x) (int)x.size() mt19937 rng(48763); vector<int> v, p, p_; string ans; int n0; void ac(int x, char c) { assert(ans[x] == '0'); x = p[x]; answer_type(x, c); x = p_[x]; ans[x] = c; } int qry() { for (int &i : v) i = p[i]; int ret = query_sample(v); for (int &i : v) i = p_[i]; return ret; } int cnt1 = 0, cnt2 = 0; int qry1(int l, int r) { assert(l <= r); ++cnt1; v.clear(); for (int i = l; i <= r; ++i) v.emplace_back(i); return qry(); } void qry2() { ++cnt2; 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) { p.clear(); for (int i = 1; i <= n; ++i) p.emplace_back(i); shuffle(p.begin(), p.end(), rng); p.emplace_back(0); reverse(p.begin(), p.end()); p_.assign(n + 1, 0); for (int i = 1; i <= n; ++i) p_[p[i]] = i; cnt1 = cnt2 = 0; n0 = n; ans.assign(n + 1, '0'); vector<int> t; t.emplace_back(0); while (1) { int l = t.back() + 2, r = n + 2; while (l < r) { int mid = (l + r) >> 1; if (qry1(t.back() + 1, mid - 1) == (mid - 1) - (t.back() + 1) + 1) l = mid + 1; else r = mid; } if (l - 1 > n) break; t.emplace_back(l - 1); ac(l - 1, 'T'); /* 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(); } assert(cnt2 <= 40); assert(cnt1 <= 280); }
#Verdict Execution timeMemoryGrader output
Fetching results...