#include <bits/stdc++.h>
#include "combo.h"
using namespace std;
// string S = "ABXYY";
// // z[i] = length of longest common prefix of s[0..N] and s[i..N]
// vector<int> zfunc(const string& s) {
// int n = (int)s.length();
// vector<int> z(n);
// z[0] = n;
// for (int i = 1, l = 0, r = 0; i < n; ++i) {
// if (i <= r)
// z[i] = min(r - i + 1, z[i - l]);
// while (i + z[i] < n && s[z[i]] == s[i + z[i]])
// ++z[i];
// if (i + z[i] - 1 > r)
// l = i, r = i + z[i] - 1;
// }
// return z;
// }
// int press(string p)
// {
// string s = S + "#" + p;
// vector<int> z = zfunc(s);
// return *max_element(z.begin() + (int)(S.size()), z.end());
// }
auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937_64 mt(seed);
long long get_random(long long l, long long r, bool non_zero = 0)
{
assert(l <= r);
long long res;
while (true)
{
res = mt() % (r - l + 1) + l;
if (non_zero && !res) continue;
break;
}
return res;
}
string guess_sequence(int N)
{
int asked = 0;
string chars = "ABXY";
string t = "";
if (press(chars.substr(0, 2)))
{
if (press(chars.substr(0, 1)))
{
t += chars[0];
chars.erase(0, 1);
}
else
{
t += chars[1];
chars.erase(1, 1);
}
}
else
{
if (press(chars.substr(2, 1)))
{
t += chars[2];
chars.erase(2, 1);
}
else
{
t += chars[3];
chars.erase(3, 1);
}
}
if (N == 1) return t;
asked += 2;
for (int i = 2; i < N; i++)
{
string a = t;
a += chars[0];
string b = t;
b += chars[1];
string s = a;
for (char c : chars)
{
b += c;
s += b;
b.pop_back();
}
asked++;
int k = press(s);
if (k == i) t += chars[0];
else if (k == i + 1) t += chars[1];
else t += chars[2];
}
if (press(t + chars.substr(0, 1)) == N)
{
t += chars[0];
}
else if (press(t + chars.substr(1, 1)) == N)
{
t += chars[1];
}
else t += chars[2];
//cout << "ASKED " << asked << '\n';
return t;
}
// int main()
// {
// cout << guess_sequence(S.size());
// return 0;
// }
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |