This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "combo.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define ld long double
#define fi first
#define se second
#define F first
#define S second
#define pii pair < int , int >
#define _ <<" "<<
#define TIME 1.0 * clock() / CLOCKS_PER_SEC
vector < char > can = {'A', 'B', 'X', 'Y'};
int st = -1;
string fir(int len){
string s;
while(len--) s += can[0];
return s;
}
string nxt(string s){
int n = s.size();
bool byl = 0;
for (int i = n - 1; i >= 0; --i)
if (s[i] != can.back()){
int pos = 0;
for (int j = 0; j < can.size(); ++j)
if (can[j] == s[i]) pos = j;
s[i] = can[pos + 1]; byl = 1;
for (int j = i + 1; j < n; ++j)
s[j] = can[0];
// cout << s << endl;
break;
}
if (!byl) return fir(n + 1);
return s;
}
bool done;
#define psi pair < string, string >
string str[5005], STA;
psi check(int len, int mxlen, string& base){
string ask;
string s = fir(len);
done = 1;
int cur = 0;
while(true){
int add = 0;
string ask1;
if (ask.size() + 1 > mxlen) break;
str[cur + 1 + base.size() + s.size() - 1] = s;
// cout << cur _ s _ ask << endl;
if (cur){
string z = fir(cur);
while(ask1.size() + ask.size() <= mxlen){
if (z.size() == cur + 1) break;
ask1 += base + s + z;
z = nxt(z);
}
} else ask1 += base + s;
// cout << s _ cur + 1 + base.size() + len - 1 _ mxlen _ ask.size() _ ask1.size() << endl;
++cur;
if (ask1.size() + ask.size() > mxlen){
done = 0;
// cout << s << endl;
return make_pair(ask, s);
}
ask += ask1;
// vis.pb(s);
s = nxt(s);
// if (cur == 2) break;
}
// cout << str[4]<<endl;
return make_pair(ask, s);
}
mt19937_64 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
std::string guess_sequence(int N) {
int n = N, kol = 0;
string base;
string now = "A";
// if (n == 1){
if (press("A") == 1) base = "A"; else
if (press("B") == 1) base = "B"; else
if (press("X") == 1) base = "X"; else
base = "Y";
STA = base;
if (n == 1) return base;
for (int i = 0; i < can.size(); ++i)
if (can[i] == base.back()){
can.erase(can.begin() + i);
break;
}
while(base.size() + 1 != n){
int ost = n - base.size();
string ask;
int l = 1;
while(check(l, n * 4, base).S.size() > l) ++l;
if (l == 1) break;
--l;
auto otv = check(l, 4 * n, base);
int ans = press(otv.F);
// cout << l << " " << otv.F _ otv.S _ ans << endl;
base += str[ans];
++kol;
// if (base.size() >= 3) break;
}
// cout << base _ kol << endl;
while(base.size() != n){
string ask = base + can[0];
string dop;
for (int i = 0; i < 3; ++i){
dop += base + can[1] + can[i];
}
// cout << base _ ask _ dop << endl;
if (ask.size() + dop.size() <= 4 * n || base.size() == n){
ask += dop;
int otv = press(ask);
// cout << ask _ otv << endl;
if (otv == base.size())
base += can[2]; else
if (otv == 1 + base.size())
base += can[0]; else
base += can[1];
} else {
shuffle(can.begin(), can.end(), gen);
for (int i = 0; i < 3; ++i){
string ask = base + can[i];
// cout << base _ ask _ press(ask) << endl;
if (press(ask) == base.size() + 1){
base += can[i];
break;
}
}
}
// break;
}
return base;
}
Compilation message (stderr)
combo.cpp: In function 'std::string nxt(std::string)':
combo.cpp:29:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for (int j = 0; j < can.size(); ++j)
| ~~^~~~~~~~~~~~
combo.cpp: In function 'std::pair<std::__cxx11::basic_string<char>, std::__cxx11::basic_string<char> > check(int, int, std::string&)':
combo.cpp:53:28: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
53 | if (ask.size() + 1 > mxlen) break;
| ~~~~~~~~~~~~~~~^~~~~~~
combo.cpp:58:44: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
58 | while(ask1.size() + ask.size() <= mxlen){
| ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
combo.cpp:59:30: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
59 | if (z.size() == cur + 1) break;
| ~~~~~~~~~^~~~~~~~~~
combo.cpp:66:38: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
66 | if (ask1.size() + ask.size() > mxlen){
| ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
combo.cpp:51:13: warning: unused variable 'add' [-Wunused-variable]
51 | int add = 0;
| ^~~
combo.cpp: In function 'std::string guess_sequence(int)':
combo.cpp:93:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for (int i = 0; i < can.size(); ++i)
| ~~^~~~~~~~~~~~
combo.cpp:98:27: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
98 | while(base.size() + 1 != n){
| ~~~~~~~~~~~~~~~~^~~~
combo.cpp:102:46: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
102 | while(check(l, n * 4, base).S.size() > l) ++l;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
combo.cpp:99:13: warning: unused variable 'ost' [-Wunused-variable]
99 | int ost = n - base.size();
| ^~~
combo.cpp:113:23: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
113 | while(base.size() != n){
| ~~~~~~~~~~~~^~~~
combo.cpp:120:37: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
120 | if (ask.size() + dop.size() <= 4 * n || base.size() == n){
| ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
combo.cpp:120:61: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
120 | if (ask.size() + dop.size() <= 4 * n || base.size() == n){
| ~~~~~~~~~~~~^~~~
combo.cpp:124:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | if (otv == base.size())
| ~~~~^~~~~~~~~~~~~~
combo.cpp:126:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | if (otv == 1 + base.size())
| ~~~~^~~~~~~~~~~~~~~~~~
combo.cpp:134:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | if (press(ask) == base.size() + 1){
| ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
