#include "toxic.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define MOD 1000000007
int query_sample(std::vector<int> species);
void answer_type(int x, char c);
vector<int> T;
void f(int l, int r, int hmm){
// cout << l << ' ' << r << ' ' << hmm << '\n';
if(l == r){
if(query_sample(vector<int>{l}) == 0){
T.pb(l);
// cout << l << ' ';
answer_type(l, 'T');
}
return;
}
vector<int> v;
int m = l+r>>1;
for(int i = l; i <= m; ++i) v.pb(i);
int L = query_sample(v);
if(hmm - (m - l + 1 - L) > 0) f(m+1, r, hmm - (m - l + 1 - L));
if(L < m - l + 1) f(l, m, m - l + 1 - L);
}
void determine_type(int n){
T.clear();
vector<int> gg;
for(int i = 1; i <= n; ++i) gg.pb(i);
f(1, n, n - query_sample(gg));
vector<bool> used(n+1);
for(int x: T) used[x] = 1;
vector<int> a;
for(int i = 1; i <= n; ++i) if(!used[i]) a.pb(i);
for(int i = 0; i < a.size(); i += 8){
vector<int> cur;
cur.pb(T[0]);
for(int j = i; j < min(int(a.size()), i+8); ++j){
for(int l = 0; l < (1<<(j-i)); ++l){
cur.pb(a[j]);
}
}
// assert(cur.size() <= 300);
// cout << cur.size() << '\n';
int s = query_sample(cur);
for(int j = i; j < min(int(a.size()), i+8); ++j){
int d = (j-i);
if(s&(1<<d)){
answer_type(a[j], 'S');
}else answer_type(a[j], 'R');
}
}
}
Compilation message
toxic.cpp: In function 'void f(int, int, int)':
toxic.cpp:24:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
24 | int m = l+r>>1;
| ~^~
toxic.cpp: In function 'void determine_type(int)':
toxic.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i = 0; i < a.size(); i += 8){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Partially correct |
4 ms |
348 KB |
Partially correct |
| 3 |
Partially correct |
5 ms |
348 KB |
Partially correct |
| 4 |
Partially correct |
5 ms |
344 KB |
Partially correct |
| 5 |
Partially correct |
8 ms |
500 KB |
Partially correct |
| 6 |
Partially correct |
7 ms |
348 KB |
Partially correct |
| 7 |
Partially correct |
5 ms |
348 KB |
Partially correct |
| 8 |
Partially correct |
5 ms |
348 KB |
Partially correct |
| 9 |
Partially correct |
9 ms |
504 KB |
Partially correct |
| 10 |
Partially correct |
5 ms |
348 KB |
Partially correct |
| 11 |
Partially correct |
5 ms |
348 KB |
Partially correct |
| 12 |
Partially correct |
5 ms |
504 KB |
Partially correct |
| 13 |
Partially correct |
5 ms |
348 KB |
Partially correct |
| 14 |
Partially correct |
5 ms |
348 KB |
Partially correct |
| 15 |
Partially correct |
6 ms |
348 KB |
Partially correct |
| 16 |
Partially correct |
9 ms |
348 KB |
Partially correct |
| 17 |
Partially correct |
5 ms |
348 KB |
Partially correct |
| 18 |
Partially correct |
5 ms |
348 KB |
Partially correct |
| 19 |
Partially correct |
5 ms |
348 KB |
Partially correct |
| 20 |
Partially correct |
5 ms |
508 KB |
Partially correct |
| 21 |
Partially correct |
5 ms |
348 KB |
Partially correct |
| 22 |
Partially correct |
5 ms |
348 KB |
Partially correct |
| 23 |
Partially correct |
4 ms |
508 KB |
Partially correct |
| 24 |
Correct |
7 ms |
344 KB |
Output is correct |
| 25 |
Correct |
7 ms |
516 KB |
Output is correct |
| 26 |
Correct |
4 ms |
348 KB |
Output is correct |
| 27 |
Correct |
4 ms |
348 KB |
Output is correct |
| 28 |
Correct |
6 ms |
348 KB |
Output is correct |
| 29 |
Correct |
5 ms |
348 KB |
Output is correct |
| 30 |
Partially correct |
4 ms |
348 KB |
Partially correct |
| 31 |
Correct |
6 ms |
348 KB |
Output is correct |
| 32 |
Correct |
4 ms |
348 KB |
Output is correct |
| 33 |
Correct |
4 ms |
348 KB |
Output is correct |
| 34 |
Partially correct |
5 ms |
348 KB |
Partially correct |
| 35 |
Partially correct |
5 ms |
348 KB |
Partially correct |
| 36 |
Partially correct |
1 ms |
348 KB |
Partially correct |
