Submission #1191105

#TimeUsernameProblemLanguageResultExecution timeMemory
1191105avighnaToxic Gene (NOI23_toxic)C++20
0 / 100
0 ms324 KiB
#include "toxic.h" #include <algorithm> #include <cassert> #include <functional> #include <iostream> #include <numeric> #include <random> #include <ranges> int BinarySearchMin(int s, int e, const std::function<bool(int)> &f) { while (s < e) { int m = s + (e - s) / 2; if (f(m)) { e = m; } else { s = m + 1; } } return s; } void determine_type(int n) { std::vector<char> ans(n + 1); std::vector<int> p(n); std::iota(p.begin(), p.end(), 0); std::random_device rd; std::mt19937 gen(rd()); std::shuffle(p.begin(), p.end(), gen); // with randomized index locs, new funcs auto query = [&](std::vector<int> sample) { for (auto &i : sample) { i = p[i - 1] + 1; } return query_sample(sample); }; auto answer = [&](int i, char x) { answer_type(p[i - 1] + 1, x); }; auto create_vec = [](int s, int e) { std::vector<int> ans; for (int i = s; i <= e; ++i) { ans.push_back(i); } return ans; }; auto create_sample = [&](std::vector<int>::iterator begin, std::vector<int>::iterator end) { std::vector<int> sample; for (int bt = 0; bt < 8 and begin != end; ++bt, ++begin) { for (int j = 0; j < (1 << bt); ++j) { sample.push_back(*begin); } } return sample; }; std::vector<int> check; // normal, strong std::vector<int> naturals(n + 1); std::iota(naturals.begin(), naturals.end(), 0); int toxic_loc = 0; std::vector<int> future_queries(n + 1); for (int i = 1; i <= n; i += 8) { auto sample = create_sample(naturals.begin() + i, naturals.begin() + std::min(n + 1, i + 8)); int mask = query(sample); if (mask == sample.size()) { for (int j = i; j <= std::min(n, i + 7); ++j) { check.push_back(j); } } future_queries[i] = mask; } for (int i = 1; i <= n; i += 8) { auto sample = create_sample(naturals.begin() + i, naturals.begin() + std::min(n + 1, i + 8)); int mask = future_queries[i]; if (mask != sample.size()) { std::vector<int> idxs; for (int j = i, bt = 0; j <= std::min(n, i + 7); ++j, ++bt) { if (mask & (1 << bt)) { ans[j] = 'S'; } else { idxs.push_back(j); } } do { int pt = BinarySearchMin(0, idxs.size() - 1, [&](int j) { std::vector<int> sample; // only toxic and normal for (int k = 0; k <= j; ++k) { sample.push_back(idxs[k]); } // add some things we can basically do a free check with int k = 0; // number of things we added std::vector<int> things_rem; for (; k < 8 and !check.empty(); ++k) { for (int bt = 0; bt < (1 << k); ++bt) { sample.push_back(check.back()); } things_rem.push_back(check.back()); check.pop_back(); } int mask = query(sample); if (mask == sample.size()) { for (auto &i : things_rem) { check.push_back(i); } return false; } for (int bt = 0; bt < k; ++bt) { if (mask & (1 << bt)) { ans[things_rem[bt]] = 'S'; } else { ans[things_rem[bt]] = 'R'; } } return true; }); ans[idxs[pt]] = 'T'; toxic_loc = idxs[pt]; idxs.erase(idxs.begin() + pt); std::sort(idxs.begin(), idxs.end()); } while (query(idxs) != idxs.size()); for (int i = 0; i < idxs.size(); ++i) { ans[idxs[i]] = 'R'; } } } // for (int i = 0; i < check.size(); i += 8) { // auto sample = create_sample( // check.begin() + i, check.begin() + std::min(int(check.size()), i + // 8)); // sample.push_back(toxic_loc); // normal and strong + one toxic // auto mask = query(sample); // for (int bt = 0; bt < 8 and i + bt < check.size(); ++bt) { // if (mask & (1 << bt)) { // ans[check[i + bt]] = 'S'; // } else { // ans[check[i + bt]] = 'R'; // } // } // } for (int i = 1; i <= n; ++i) { answer(i, ans[i]); } }
#Verdict Execution timeMemoryGrader output
Fetching results...