#include <bits/stdc++.h>
using namespace std;
#define ss second
// #define DEBUG 0
// #define MAX_QUERIES 50000
// #define MAX_N 5000
// #define MAX_SIGMA 26
// static string password;
// static int n, s, numQueries;
// static stringstream msg;
// static void end(int success) {
// cout << (success ? "SUCCESS! " : "ERROR: ") << msg.str() << endl;
// exit(0);
// }
// int query(string q) {
// if (++numQueries > MAX_QUERIES) {
// msg << "Could not guess the password with " << MAX_QUERIES << " questions.";
// end(0);
// }
// int len = q.size();
// // validation
// if (len < 1 || len > n) {
// msg << "Query '" << q << "' should have length between 1 and "
// << n << " characters.";
// end(0);
// }
// for (int i = 0; i < len; i++) {
// if (q[i] < 'a' || q[i] >= 'a' + s) {
// msg << "Illegal character '" << q[i] << "' found.";
// end(0);
// }
// }
// // while possible, advance one character in q and find its next
// // occurrence in password
// int i = 0, j = 0, plen = password.size();
// while (i < plen && j < len) {
// while ((i < plen) && (password[i] != q[j])) {
// i++;
// }
// if (i < plen) { /* found a match */
// i++;
// j++;
// }
// }
// if (DEBUG) {
// cout << "Question #" << numQueries << " [" << q << "] answer " << j << endl;
// }
// return j;
// }
int query(string q);
string merge(string a,string b){
string s="",pas="";
int curr=b.size()-1;
for(int i=a.size()-1;i>=0;i--){
while(curr>=0){
s=a.substr(0,i+1)+b.substr(curr);
// cout<<s<<" "<<b.size()<<endl;
if(query(s)==s.size()){
pas+=b[curr];
curr--;
}else{
break;
}
}
pas+=a[i];
}
// cout<<curr<<endl;
while(curr>=0){
pas+=b[curr];
curr--;
}
reverse(pas.begin(),pas.end());
return pas;
}
string guess(int n, int s){
cin>>n>>s;
string s1;
set <pair <int,string > > se;
int l;
for(int j=1;j<=s;j++){
s1="";
for(int i=1;i<=n;i++){
s1+=char(j+'a'-1);
}
l=query(s1);
s1="";
// cout<<l<<endl;
for(int i=1;i<=l;i++){
s1+=char(j+'a'-1);
}
se.insert(make_pair(s1.size(),s1));
}
// cout<<"YES"<<endl;
while(se.size()>=2){
auto a=(*(se.begin()));
se.erase(se.begin());
auto b=(*(se.begin()));
se.erase(se.begin());
// cout<<a.ss<<" "<<b.ss<<endl;
s1=merge(a.ss,b.ss);
se.insert(make_pair(s1.size(),s1));
}
return (*(se.begin())).ss;
}
// int main() {
// cin>> n >> s >> password;
// assert(n && s && !password.empty());
// string answer = guess(n, s);
// if (DEBUG) {
// cout << "Your answer: [" << answer << "]\n";
// }
// if (answer.compare(password)) {
// msg << "Your answer was [" << answer
// << "] which does not match the password [" << password << "].";
// end(0);
// } else {
// msg << "You guessed the password with " << numQueries << " queries.";
// end(1);
// }
// return 0;
// }
Compilation message
password.cpp: In function 'std::string merge(std::string, std::string)':
password.cpp:66:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | if(query(s)==s.size()){
| ~~~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
0 ms |
344 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
0 ms |
344 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
0 ms |
344 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
0 ms |
344 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
0 ms |
344 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
