#include "toxic.h"
#include <bits/stdc++.h>
using namespace std;
const int K = 8;
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)
{
vector<int> ord(n);
iota(ord.begin(), ord.end(), 1);
// random_shuffle(ord.begin(), ord.end());
string ans(n + 1, 'R');
int tt = -1;
vector<int> stk;
int i = 0;
while (i < n)
{
int j = min(n, i + K);
{
vector<int> qry;
for (int k = i; k < j; k++)
{
qry.push_back(ord[k]);
}
int res = query_sample(encode(qry));
if (res == (1 << qry.size()) - 1)
{
stk.insert(stk.end(), qry.begin(), qry.end());
i = j;
continue;
}
}
cerr << "HERE" << endl;
auto make_query = [&](int mid)
{
vector<int> qry;
for (int k = i; 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;
};
int l = i, r = j;
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
{
r = mid;
}
}
vector<int> qry = make_query(l);
auto tmp = encode(qry);
tmp.push_back(ord[l]);
int res = query_sample(tmp);
for (int k = 0; k < qry.size(); k++)
{
ans[qry[k]] = (res >> k & 1) ? 'S' : 'R';
}
cerr << "ans " << ans << endl;
ans[ord[l]] = 'T';
int x = min((int)stk.size(), K - (l - i + 1));
for (int k = 0; k < x; k++)
{
stk.pop_back();
}
cerr << "OK " << l << ' ' << qry[l - i] << endl;
i = l + 1;
tt = ord[l];
}
cerr << ans << endl;
for (int j = 0; j < stk.size(); j++)
{
cerr << stk[j] << endl;
}
cerr << "tt " << tt << endl;
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';
}
}
cerr << ans << endl;
for (int j = 1; j <= n; j++)
{
answer_type(j, ans[j]);
}
}
Compilation message
toxic.cpp: In function 'void determine_type(int)':
toxic.cpp:79:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for (int k = 0; k < qry.size(); k++)
| ~~^~~~~~~~~~~~
toxic.cpp:95:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for (int j = 0; j < stk.size(); j++)
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
