#include "toxic.h"
#include<bits/stdc++.h>
using namespace std;
using ll = int;
using ull = unsigned long long;
using ld = long double;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
#define MP make_pair
ll ans[310];
ll wow = 0;
ll query(vector <ll> all){
wow++;
return query_sample(all);
}
//0 thuong 1 doc 2 manh
void solve(vector <ll> all){
if (sz(all) == 1){ans[all.back()]=1;return;}
ll mid = sz(all)/2;
vector <ll> L;
vector <ll> R;
for (ll i = 0;i < mid;i++)L.push_back(all[i]);
for (ll i = mid;i < sz(all);i ++)R.push_back(all[i]);
if (query(L)!=sz(L)){
solve(L);
}
else solve(R);
}
void determine_type(int n){
wow = 0;
for (ll i = 1;i <= n;i ++)ans[i] = -1;
vector <ll> pos;
for (ll i= 1;i <= n;i ++){
pos.push_back(i);
}
while (sz(pos)){
vector <ll> cur;
while (sz(pos) && sz(cur) < 8){cur.push_back(pos.back());pos.pop_back();}
if (query(cur) != sz(cur)){
solve(cur);
for (auto x:cur)if (ans[x]==-1)pos.push_back(x);
}
cout<<sz(pos)<<endl;
}
// assert(wow <= 90 + 35);
// cout<<"WHAT "<<wow<<endl;
ll poison = -1;
vector <ll> rem;
for (ll i = 1;i <= n;i ++){
if (ans[i] == 1){
poison = i;
}
else{
rem.push_back(i);
}
}
// for (auto x:rem)cout<<x<<' ';
// cout<<'\n';
while (sz(rem)){
vector <ll> cur;
while (sz(rem) && sz(cur) < 8){cur.push_back(rem.back());rem.pop_back();}
vector <ll> all;
for (ll j = 0;j < sz(cur);j ++){
for (ll k = 0;k < MASK(j);k ++){
all.push_back(cur[j]);
}
}
all.push_back(poison);
ll x = query(all);
for (ll j = 0;j < sz(cur);j ++){
if (BIT(x,j)){
ans[cur[j]] = 2;
}
else ans[cur[j]] = 0;
}
}
for (ll i = 1;i <= n;i ++){
if (ans[i]==0)answer_type(i,'R');
if (ans[i]==2)answer_type(i,'S');
if (ans[i]==1)answer_type(i,'T');
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Do not print anything to stdout |
| 2 |
Halted |
0 ms |
0 KB |
- |
