#include "toxic.h"
// MagicDark
#include <bits/stdc++.h>
#define debug cerr << "[" << __LINE__ << "] "
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> inline void chkmax(T& x, T y) {x = max(x, y);}
template <typename T> inline void chkmin(T& x, T y) {x = min(x, y);}
template <typename T> inline void read(T &x) {
x = 0; int f = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
x *= f;
}
mt19937 mrand(1);//chrono::steady_clock::now().time_since_epoch().count());
inline int rnd(int l, int r) {return mrand() % (r - l + 1) + l;}
int t[310];
vector <int> g;
void solve(int l, int r) {
if (l == r) {
g.push_back(l);
return;
}
int mid = (l + r) >> 1;
vector <int> p, q;
F(i, l, mid) p.push_back(t[i]);
F(i, mid + 1, r) q.push_back(t[i]);
if (query_sample(p) != p.size()) solve(l, mid);
if (query_sample(q) != q.size()) solve(mid + 1, r);
}
vector <int> f;
void dot(int l, int r) {
vector <int> w;
F(i, l, r) w.push_back(f[i - 1]);
w.push_back(t[g[0]]);
// for (int i: w) cout << i << " "; cout << endl;
int f = query_sample(w);
// debug << l << " " << r << " " << f << endl;
if (f == 0) {
F(i, l, r) answer_type(::f[i - 1], 'R');//, debug << i << endl;
return;
}
if (f == r - l + 1) {
F(i, l, r) answer_type(::f[i - 1], 'S');//, debug << i << endl;
return;
}
int mid = (l + r) >> 1;
dot(l, mid), dot(mid + 1, r);
}
void determine_type(int n) {
f.clear();
g.clear();
F(i, 1, n) t[i] = i;
shuffle(t + 1, t + n + 1, mrand);
solve(1, n);
for (int i: g) answer_type(t[i], 'T');//, debug << i << endl;
// for (int i: g) debug << i << endl;
// g.insert(g.begin(), 0);
// g.push_back(n + 1);
F(i, 1, n)
if (!count(all(g), i)) f.push_back(t[i]);
int B = n;
for (int l = 1, r; l <= f.size(); l = r + 1) {
r = min((int) f.size(), l + B - 1);
dot(l, r);
}
// F(i, 0, SZ(g) - 1)
// if (g[i] + 1 != g[i + 1]) dot(g[i] + 1, g[i + 1] - 1);
}
Compilation message
toxic.cpp: In function 'void solve(int, int)':
toxic.cpp:34:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | if (query_sample(p) != p.size()) solve(l, mid);
| ~~~~~~~~~~~~~~~~^~~~~~~~~~~
toxic.cpp:35:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | if (query_sample(q) != q.size()) solve(mid + 1, r);
| ~~~~~~~~~~~~~~~~^~~~~~~~~~~
toxic.cpp: In function 'void determine_type(int)':
toxic.cpp:69:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (int l = 1, r; l <= f.size(); l = r + 1) {
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Partially correct |
3 ms |
348 KB |
Partially correct |
| 3 |
Partially correct |
3 ms |
524 KB |
Partially correct |
| 4 |
Incorrect |
2 ms |
508 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
