#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
int m;
string suf,pref;
int query(string str);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<string> sub(27);
int par[27];
int PAR(int x) {
if (par[x] == x) return x;
return PAR(par[x]);
}
void removeF(string &s){
reverse(all(s));
if (s.size())
s.pop_back();
reverse(all(s));
return;
}
void join(int x,int y) {
x = PAR(x), y = PAR(y);
if (sub[x].size() > sub[y].size())
swap(x,y);
par[x] = y;
int tot = sub[x].size() + sub[y].size();
string pref;
int cur = sub[y].size();
for (int i = 0;pref.size() < tot && i < sub[x].size() ;i++) {
string P = pref + sub[x][i];
P += sub[y];
//int F;
int F = query(P);
if (F > cur) {
pref += sub[x][i];
cur = F;
}else {
pref += sub[y][0];
removeF(sub[y]);
i--;
}
}
sub[y] = pref;
}
string guess(int n, int s) {
string pref,P;
for (int i = 0;i < 26; i++) {
par[i] = i;
for (int j = 0; j < n; j++)
P+='a'+ i;
//int x;
int x = query(P);
P.clear();
for (int j = 0; j < 26; j++)
P+='a' + i;
sub[i] = P;
P.clear();
}
for (int i = 1; i < 26; i++) {
join(i,1);
}
int x = PAR(0);
return sub[x];
vector<char> D;
for (char i = 'a'; i < 'a' + s ; i++)
D.pb(i);
shuffle(all(D),rng);
map<char,int> mp;
for (int i = 0;i < s; i++) mp[D[i]] = i;
char fs = 'a';
for (; pref.size() + suf.size() < n; ) {
int len = suf.size() + pref.size();
char LAST = ((int)pref.size() ? pref.back() : 'a');
int cur = len;
// vector<char> D = T;
for (int z = 1; z + pref.size() + suf.size() <= n;) {
bool flag = 0;
vector<char> Q;
// shuffle(D.begin(),D.end(),rng);
for (int b= max((pref.size() ? mp[pref.back()] : 0),(suf.size() ? mp[suf[0]] : 0)); b < s; b++){
char c = D[b];
/// for (char c : D) {
P = pref + c;
P += suf;
int F = query(P);
if (F > cur) {
LAST = c;
pref += c;
cur = F;
flag = 1;
break;
}
// else Q.pb(c);
}
// for (char c : Q) D.erase(find(all(D),c));
if (flag == 0) break;
}
reverse(all(suf));
if (pref.size())
suf+=pref.back();
reverse(all(suf));
if (pref.size())
pref.pop_back();
if (pref.size() + suf.size() == n) {
pref += suf;
int Z = query(pref);
return pref;
}
}
pref += suf;
int z = query(pref);
return pref;
}
/*
main() {
ios::sync_with_stdio(0);
cin.tie(0);
}*/
Compilation message
password.cpp: In function 'void join(int, int)':
password.cpp:36:29: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
36 | for (int i = 0;pref.size() < tot && i < sub[x].size() ;i++) {
| ~~~~~~~~~~~~^~~~~
password.cpp:36:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for (int i = 0;pref.size() < tot && i < sub[x].size() ;i++) {
| ~~^~~~~~~~~~~~~~~
password.cpp: In function 'std::string guess(int, int)':
password.cpp:59:7: warning: unused variable 'x' [-Wunused-variable]
59 | int x = query(P);
| ^
password.cpp:78:34: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
78 | for (; pref.size() + suf.size() < n; ) {
| ~~~~~~~~~~~~~~~~~~~~~~~~~^~~
password.cpp:83:48: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
83 | for (int z = 1; z + pref.size() + suf.size() <= n;) {
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
password.cpp:111:32: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
111 | if (pref.size() + suf.size() == n) {
| ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
password.cpp:113:8: warning: unused variable 'Z' [-Wunused-variable]
113 | int Z = query(pref);
| ^
password.cpp:80:8: warning: variable 'LAST' set but not used [-Wunused-but-set-variable]
80 | char LAST = ((int)pref.size() ? pref.back() : 'a');
| ^~~~
password.cpp:77:7: warning: unused variable 'fs' [-Wunused-variable]
77 | char fs = 'a';
| ^~
password.cpp:118:6: warning: unused variable 'z' [-Wunused-variable]
118 | int z = query(pref);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
384 KB |
Token "ppppppppppppppp" doesn't correspond to pattern "[a-o]{1,15}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
380 KB |
Token "cccccccccccccccccccccccccccccccccccccccccccccccccc" doesn't correspond to pattern "[a-b]{1,50}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
384 KB |
Token "mmmmmmmmmmmmmmmmmmmmmmmmmmmmmm...mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm" doesn't correspond to pattern "[a-l]{1,1000}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
384 KB |
Token "ppppppppppppppp" doesn't correspond to pattern "[a-o]{1,15}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
384 KB |
Token "ppppppppppppppp" doesn't correspond to pattern "[a-o]{1,15}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
