Submission #1132676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132676		MrAndria	Password (RMI18_password)	C++20	0 / 100	16 ms	452 KiB

password

#include <bits/stdc++.h>
using namespace std;
// #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 str);
string merg(string a,string b){
    string s2="",pas="";
    int curr=b.size()-1;
    // cout<<a<<" "<<b<<" 5 "<<a.size()<<endl;
    for(int i=a.size();i>0;i--){
// 		cout<<"NO2"<<endl;
        while(curr>=0){
// 			cout<<"NO2"<<endl;
            s2="";
            // cout<<"NO2"<<endl;
            for(int i1=0;i1<=i-1;i1++){
				// cout<<a[i1]<<" ";
                s2.push_back(a[i1]);
            }
            // cout<<"NO2"<<endl;
            for(int i1=curr;i1<=b.size()-1;i1++){
                s2.push_back(b[i1]);
            }
            
            // cout<<"NO2"<<endl;
            // cout<<s<<" "<<b.size()<<endl;
            if(query(s2)==s2.size()){
                pas.push_back(b[curr]);
                curr--;
            }else{
                break;
            }
        }
        pas.push_back(a[i-1]);
        // cout<<i<<" HERE"<<endl;

    }
    // cout<<curr<<endl;
    while(curr>=0){
        pas+=b[curr];
        curr--;
    }
    reverse(pas.begin(),pas.end());
    return pas;
}
string guess(int n, int 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.push_back(char(j+'a'-1));
        }

        l=query(s1);
        s1="";
        for(int i=1;i<=l;i++){
            s1.push_back(char(j+'a'-1));
        }
        if(s1.size())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<<"NO"<<endl;
        s1=merg(a.second,b.second);
        // cout<<"NO1"<<endl;
        se.insert(make_pair(s1.size(),s1));
    }
    if(se.size()==0)assert(0);
    return (*(se.begin())).second;
}
// int main() {
//   cin>> n >> s >> password;
// //   assert(n && s && !password.empty());

//   string answer = guess(n, s);
//   cout<<answer<<endl;

// //   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;
// }

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20