# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
940914 | Tuanlinh123 | Toxic Gene (NOI23_toxic) | C++17 | 10 ms | 604 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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(170306);
void determine_type(ll n)
{
ll lo=1, hi=n;
auto queryrange=[&](ll l, ll r)
{
vector <ll> ask(r-l+1);
iota(ask.begin(), ask.end(), l);
return query_sample(ask);
};
while (hi>lo)
{
ll mid=(lo+hi)/2;
if (queryrange(lo, mid)==mid-lo+1)
lo=mid+1;
else hi=mid;
}
vector <char> ans(n+1, 0);
ans[lo]='T';
for (ll i=1; i<=n; i+=8)
{
vector <ll> ask; ask.pb(lo);
for (ll j=i; j<=n && j<i+8; j++)
for (ll k=0; k<1<<(j-i); k++)
ask.pb(j);
ll x=query_sample(ask);
for (ll j=i; j<=n && j<i+8; j++)
if (x&1<<(j-i))
ans[j]='S';
}
vector <ll> idx;
for (ll i=1; i<=n; i++)
if (!ans[i])
idx.pb(i);
shuffle(idx.begin(), idx.end(), rng);
if (idx.size()<=200)
{
for (ll i:idx)
{
vector <ll> ask(1, i);
if (query_sample(ask)) ans[i]='R';
else ans[i]='T';
}
}
else
{
auto queryran=[&](ll l, ll r)
{
vector <ll> ask;
for (ll i=l; i<=r; i++)
ask.pb(idx[i]);
return query_sample(ask);
};
function <void(ll, ll)> find=[&](ll l, ll r)
{
ll x=queryran(l, r);
if (x>0)
{
for (ll i=l; i<=r; i++)
ans[idx[i]]='R';
return;
}
if (l==r) {ans[idx[l]]='T'; return;}
ll mid=(l+r)/2;
find(l, mid), find(mid+1, r);
}; find(0, sz(idx)-1);
}
for (ll i=1; i<=n; i++)
answer_type(i, ans[i]);
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |