#include<bits/stdc++.h>
#include "toxic.h"
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 300 + 10, T = 8;
int order[N], ans[N];
bool not_toxic[N];
char type[3] = {'R', 'S', 'T'};
mt19937 rng(324857235);
#ifdef ngu
int cnt_query;
char a[N], b[N];
int query_sample(vector<int> species) {
cnt_query++;
bool toxic = 0;
for(int &j : species) toxic |= a[j] == 'T';
int ret = 0;
for(int &j : species) {
if (a[j] == 'S') ret++;
else if (a[j] == 'R' && !toxic) ret++;
}
return ret;
}
void answer_type(int x, char c) {
b[x] = c;
}
#endif // ngu
vector<int> strong_regular, toxic_regular;
bool check (vector<int> candidate) {
vector<int> share;
while (!strong_regular.empty() && share.size() < T) {
share.push_back(strong_regular.back());
strong_regular.pop_back();
}
for(int j = 0; j < share.size(); j++) {
int cnt = 1 << j;
while (cnt--) candidate.push_back(share[j]);
}
int result = query_sample(candidate);
if (result == candidate.size()) {
for(int &j : share) strong_regular.push_back(j);
for(int &j : candidate) not_toxic[j] = 1;
return false;
}
for(int j = 0; j < share.size(); j++) {
if (result >> j & 1) ans[share[j]] = 1;
}
return true;
}
int Search (vector<int> candidate) {
if (candidate.size() == 1) return candidate.back();
vector<int> left, right;
int mid = (int) candidate.size() / 2;
for(int i = 0; i < mid; i++) left.push_back(candidate[i]);
for(int i = mid; i < candidate.size(); i++) right.push_back(candidate[i]);
if (!left.empty() && check(left)) return Search(left);
return Search(right);
}
void determine_type (int n) {
for(int i = 1; i <= n; i++) order[i] = i, ans[i] = not_toxic[i] = 0;
shuffle(order + 1, order + n + 1, rng);
for(int i = 1; i <= n; i += T) {
// cout << cnt_query << endl;
vector<int> ask;
int border = min(i + T - 1, n);
for(int j = i; j <= border; j++) {
int cnt = 1 << j - i;
while (cnt--) ask.push_back(order[j]);
}
int result = query_sample(ask);
int full = 1 << (border - i + 1); full--;
// cout << result << " " << i << endl;
if (result == full) {
for(int j = i; j <= border; j++) strong_regular.push_back(order[j]);
}
else {
vector<int> candidate;
for(int j = i; j <= border; j++) {
int delta = j - i;
if (result >> delta & 1) ans[order[j]] = 1;
else candidate.push_back(order[j]);
}
int x = Search(candidate);
ans[x] = 2;
for(int &j : candidate) if (j != x && not_toxic[j] == 0) toxic_regular.push_back(j);
}
}
// for(int i = 1; i <= n; i++) cout << ans[i] << " "; cout << endl;
while (!toxic_regular.empty()) {
vector<int> candidate;
while (!toxic_regular.empty() && candidate.size() < 8) {
candidate.push_back(toxic_regular.back());
toxic_regular.pop_back();
}
if (check(candidate)) {
int x = Search(candidate);
ans[x] = 2;
for(int &j : candidate) if (j != x && not_toxic[j] == 0) toxic_regular.push_back(j);
}
}
int toxic = 0;
for(int i = 1; i <= n; i++) if (ans[i] == 2) toxic = i;
// cout << toxic << endl;
while (!strong_regular.empty()) {
vector<int> cur;
while (!strong_regular.empty() && cur.size() < T) {
cur.push_back(strong_regular.back());
strong_regular.pop_back();
}
vector<int> ask = {toxic};
for(int j = 0; j < cur.size(); j++) {
int cnt = 1 << j;
while (cnt--) ask.push_back(cur[j]);
}
int result = query_sample(ask);
for(int j = 0; j < cur.size(); j++) {
if (result >> j & 1) ans[cur[j]] = 1;
else ans[cur[j]] = 0;
}
}
// for(int i = 1; i <= n; i++) cout << ans[i] << " "; cout << endl;
for(int i = 1; i <= n; i++) {
answer_type(i, type[ans[i]]);
}
}
#ifdef ngu
int main() {
freopen ("task.inp", "r", stdin);
freopen ("task.out", "w", stdout);
int t; cin >> t;
while (t--) {
cnt_query = 0;
int n; cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
determine_type(n);
for(int i = 1; i <= n; i++) assert(a[i] == b[i]);
for(int i = 1; i <= n; i++) cout << b[i] << " "; cout << endl;
// assert(cnt_query <= 600);
assert(cnt_query <= 150);
cerr << cnt_query << endl;
}
}
#endif // ngu
Compilation message
toxic.cpp: In function 'bool check(std::vector<int>)':
toxic.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int j = 0; j < share.size(); j++) {
| ~~^~~~~~~~~~~~~~
toxic.cpp:50:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | if (result == candidate.size()) {
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
toxic.cpp:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(int j = 0; j < share.size(); j++) {
| ~~^~~~~~~~~~~~~~
toxic.cpp: In function 'int Search(std::vector<int>)':
toxic.cpp:66:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int i = mid; i < candidate.size(); i++) right.push_back(candidate[i]);
| ~~^~~~~~~~~~~~~~~~~~
toxic.cpp: In function 'void determine_type(int)':
toxic.cpp:79:24: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
79 | int cnt = 1 << j - i;
| ~~^~~
toxic.cpp:128:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | for(int j = 0; j < cur.size(); j++) {
| ~~^~~~~~~~~~~~
toxic.cpp:133:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | for(int j = 0; j < cur.size(); j++) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
11 ms |
348 KB |
Output is correct |
| 3 |
Correct |
8 ms |
348 KB |
Output is correct |
| 4 |
Correct |
8 ms |
348 KB |
Output is correct |
| 5 |
Correct |
8 ms |
348 KB |
Output is correct |
| 6 |
Correct |
8 ms |
348 KB |
Output is correct |
| 7 |
Correct |
8 ms |
348 KB |
Output is correct |
| 8 |
Correct |
9 ms |
348 KB |
Output is correct |
| 9 |
Correct |
10 ms |
348 KB |
Output is correct |
| 10 |
Correct |
9 ms |
348 KB |
Output is correct |
| 11 |
Correct |
8 ms |
348 KB |
Output is correct |
| 12 |
Correct |
9 ms |
348 KB |
Output is correct |
| 13 |
Correct |
8 ms |
348 KB |
Output is correct |
| 14 |
Correct |
8 ms |
348 KB |
Output is correct |
| 15 |
Correct |
8 ms |
348 KB |
Output is correct |
| 16 |
Correct |
8 ms |
548 KB |
Output is correct |
| 17 |
Correct |
8 ms |
456 KB |
Output is correct |
| 18 |
Correct |
8 ms |
348 KB |
Output is correct |
| 19 |
Correct |
9 ms |
348 KB |
Output is correct |
| 20 |
Correct |
8 ms |
456 KB |
Output is correct |
| 21 |
Correct |
7 ms |
348 KB |
Output is correct |
| 22 |
Correct |
8 ms |
348 KB |
Output is correct |
| 23 |
Correct |
6 ms |
348 KB |
Output is correct |
| 24 |
Correct |
8 ms |
452 KB |
Output is correct |
| 25 |
Correct |
8 ms |
348 KB |
Output is correct |
| 26 |
Correct |
9 ms |
348 KB |
Output is correct |
| 27 |
Correct |
9 ms |
552 KB |
Output is correct |
| 28 |
Correct |
7 ms |
344 KB |
Output is correct |
| 29 |
Correct |
8 ms |
344 KB |
Output is correct |
| 30 |
Correct |
8 ms |
348 KB |
Output is correct |
| 31 |
Correct |
9 ms |
348 KB |
Output is correct |
| 32 |
Correct |
11 ms |
548 KB |
Output is correct |
| 33 |
Correct |
10 ms |
348 KB |
Output is correct |
| 34 |
Correct |
8 ms |
348 KB |
Output is correct |
| 35 |
Correct |
8 ms |
348 KB |
Output is correct |
| 36 |
Correct |
1 ms |
348 KB |
Output is correct |
