#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<char> D;
bool check(int x) {
/* string P = pref + D[x];
P += suf;
if (P.size() <= n) {
int z = query(P);
if (z > cur )
return 1;
}
return 0;*/
return 0;
}
string guess(int n, int s) {
string P;
// 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);
/* int lo = max((pref.size() ? mp[pref.back()] : 0),(suf.size() ? mp[suf[0]] : 0));
int hi = s-1;
while (lo < hi) {
int mid = (lo + hi)/2;
if (check(mid))
}*/
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) {
if (pref.size() + suf.size() + 1 == n) {
P = pref + c;
P += suf;
int F = query(P);
if (F > cur) {
LAST = c;
pref += c;
cur = F;
flag = 1;
break;
}
}else if (pref.size() + suf.size() + 2 <= n){
P = pref + c;
P += c;
P += suf;
int F = query(P);
if (F > cur + 1) {
LAST = c;
pref += c;
pref += c;
cur = F;
flag = 1;
break;
}else 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 'std::string guess(int, int)':
password.cpp:36:34: 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 (; pref.size() + suf.size() < n; ) {
| ~~~~~~~~~~~~~~~~~~~~~~~~~^~~
password.cpp:41:48: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
41 | for (int z = 1; z + pref.size() + suf.size() <= n;) {
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
password.cpp:55:37: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
55 | if (pref.size() + suf.size() + 1 == n) {
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
password.cpp:66:42: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
66 | }else if (pref.size() + suf.size() + 2 <= n){
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
password.cpp:97:32: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
97 | if (pref.size() + suf.size() == n) {
| ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
password.cpp:99:8: warning: unused variable 'Z' [-Wunused-variable]
99 | int Z = query(pref);
| ^
password.cpp:38:8: warning: variable 'LAST' set but not used [-Wunused-but-set-variable]
38 | char LAST = ((int)pref.size() ? pref.back() : 'a');
| ^~~~
password.cpp:35:7: warning: unused variable 'fs' [-Wunused-variable]
35 | char fs = 'a';
| ^~
password.cpp:104:6: warning: unused variable 'z' [-Wunused-variable]
104 | int z = query(pref);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
434 ms |
256 KB |
Could not guess the password with 50000 queries. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
385 ms |
256 KB |
Could not guess the password with 50000 queries. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
500 ms |
384 KB |
Could not guess the password with 50000 queries. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
434 ms |
256 KB |
Could not guess the password with 50000 queries. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
434 ms |
256 KB |
Could not guess the password with 50000 queries. |
| 2 |
Halted |
0 ms |
0 KB |
- |
