| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 951323 | browntoad | Toxic Gene (NOI23_toxic) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "toxic.h"
#include <bits/stdc++.h>
using namespace std;
const int K = 8, T = 30;
vector<int> encode(vector<int> qry)
{
int n = qry.size();
vector<int> ret;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < (1 << i); j++)
{
ret.push_back(qry[i]);
}
}
return ret;
}
void determine_type(int n)
{
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> ord(n);
iota(ord.begin(), ord.end(), 1);
string ans(n + 1, 'R');
int cnt = 0;
int tt = -1;
vector<int> stk;
int i = 0;
while (cnt < T && i < n)
{
// srand(mt19937(time(0))() + 864197532);
random_shuffle(ord.begin(), ord.begin() + i, rng);
int j = min(n, i + K);
int xx = -1;
{
vector<int> qry;
for (int k = i; k < j; k++)
{
qry.push_back(ord[k]);
}
int x = min(stk.size(), K - qry.size());
for (int k = 0; k < x; k++)
{
qry.push_back(stk.end()[-1 - k]);
}
xx = query_sample(encode(qry));
if (xx == (1 << qry.size()) - 1)
{
stk.insert(stk.end(), qry.begin(), qry.end());
i = j;
continue;
}
else
{
for (int k = j - i; k < qry.size(); k++)
{
ans[qry[k]] = (xx >> k & 1) ? 'S' : 'R';
}
for (int k = 0; k < x; k++)
{
stk.pop_back();
}
}
}
int l = i, r = j;
auto make_query = [&](int mid)
{
vector<int> qry;
for (int k = l; k < mid; k++)
{
qry.push_back(ord[k]);
}
int x = min(stk.size(), K - qry.size());
for (int k = 0; k < x; k++)
{
qry.push_back(stk.end()[-1 - k]);
}
return qry;
};
while (l < r - 1)
{
int mid = (l + r) / 2;
vector<int> qry = make_query(mid);
int res = query_sample(encode(qry));
if (res == (1 << qry.size()) - 1)
{
l = mid;
}
else
{
int x = qry.size() - (mid - l);
for (int k = mid - l; k < qry.size(); k++)
{
ans[qry[k]] = (res >> k & 1) ? 'S' : 'R';
}
for (int k = 0; k < x; k++)
{
stk.pop_back();
}
r = mid;
}
}
for (int k = 0; k < l - i; k++)
{
ans[ord[i + k]] = (xx >> k & 1) ? 'S' : 'R';
}
ans[ord[l]] = 'T';
i = l + 1;
tt = ord[l];
cnt++;
}
while (i < n)
{
stk.push_back(ord[i++]);
}
while (stk.size())
{
int x = min((int)stk.size(), K);
vector<int> qry;
for (int k = 0; k < x; k++)
{
qry.push_back(stk.back());
stk.pop_back();
}
auto tmp = encode(qry);
tmp.push_back(tt);
int res = query_sample(tmp);
for (int k = 0; k < (int)qry.size(); k++)
{
ans[qry[k]] = (res >> k & 1) ? 'S' : 'R';
}
}
for (int j = 1; j <= n; j++)
{
answer_type(j, ans[j]);
}
}