#include "toxic.h"
#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;
mt19937_64 rng(11092001);
void determine_type(ll n)
{
vector <char> ans(n+1, 0);
vector <ll> idx(n);
iota(idx.begin(), idx.end(), 1);
shuffle(idx.begin(), idx.end(), rng);
ll len=8, toxic=0;
auto queryran=[&](ll l, ll r)
{
vector <ll> ask;
for (ll i=l; i<=r; i++)
ask.pb(idx[i]);
return query_sample(ask);
};
for (ll i=0; i<sz(idx); i+=len)
{
vector <ll> ask;
for (ll j=i; j<sz(idx) && j<i+len; j++)
for (ll k=0; k<1<<(j-i); k++)
ask.pb(idx[j]);
ll x=query_sample(ask);
if (x==ask.size()) continue;
for (ll j=i; j<sz(idx) && j<i+len; j++)
if (x&1<<(j-i)) ans[idx[j]]='S';
ll p=i, en=min(sz(idx), i+len)-1;
while (1)
{
if (p==en) break;
if (queryran(p, en)==en-p+1) break;
ll lo=p, hi=en;
while (hi>lo)
{
ll mid=(lo+hi)/2;
if (queryran(p, mid)==mid-p+1) lo=mid+1;
else hi=mid;
}
ans[idx[lo]]='T', p=lo+1, toxic=idx[lo];
}
for (ll j=i; j<sz(idx) && j<i+len; j++)
if (!ans[idx[j]]) ans[idx[j]]='R';
}
idx.clear();
for (ll i=1; i<=n; i++)
if (!ans[i]) idx.pb(i);
shuffle(idx.begin(), idx.end(), rng);
for (ll i=0; i<sz(idx); i+=len)
{
vector <ll> ask; ask.pb(toxic);
for (ll j=i; j<sz(idx) && j<i+len; j++)
for (ll k=0; k<1<<(j-i); k++)
ask.pb(idx[j]);
ll x=query_sample(ask);
for (ll j=i; j<sz(idx) && j<i+len; j++)
{
if (x&1<<(j-i)) ans[idx[j]]='S';
else ans[idx[j]]='R';
}
}
for (ll i=1; i<=n; i++)
answer_type(i, ans[i]);
}
Compilation message
toxic.cpp: In function 'void determine_type(int)':
toxic.cpp:35:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | if (x==ask.size()) continue;
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
