Submission #251360

#	Time	Username	Problem	Language	Result	Execution time	Memory
251360		dantoh000	Password (RMI18_password)	C++14	100 / 100	557 ms	776 KiB

password

#include <bits/stdc++.h>
using namespace std;
int ct[26];
int query(string str);
vector<char> Q;
vector<char> T;
vector<string> pq;
bool query(){
    string str = "";
    for (auto x : Q) str += x;
    for (int i = T.size()-1; i >= 0; i--) str += T[i];
    return query(str) == str.size();
}
string merge(string s, string t){
    Q.clear();
    string test = ""; test += s[0];
    for (auto x : t) test += x;
    if (s.size() == 0 || query(test) != t.size()+1){
        swap(s,t);
    }
    int n = s.size(), m = t.size();
    int cur = 0;
    for (int i = n-1; i >= 0; i--){
        T.push_back(s[i]);
    }
    for (int i = 0; i < n-1; i++){
        Q.push_back(s[i]);
        T.pop_back();
        //printf("before adding s %c\n",s[i]);
        while (cur < m){
            Q.push_back(t[cur]);
            if (query()) {
                //printf("adding t %c\n",t[cur]);
                cur++;
            }
            else {
                Q.pop_back();
                break;
            }
        }
    }
    Q.push_back(s[n-1]);
    T.pop_back();
    while (cur < m){
        Q.push_back(t[cur++]);
    }

    string ans= "";
    for (auto x : Q) ans += x;
    //cout << "merged " << s  << " and " << t << ", " << ans << endl;
    return ans;
}
bool cmp(string a, string b){
    return a.size() > b.size();
}
string guess(int n, int s){
    string q = "";
    int sum = 0;
    for (int i = 0; i < s-1; i++){
        q = "";
        for (ct[i] = 1; ct[i] <= n; ct[i]++){
            q += (i+'a');
            if (query(q) != ct[i]) {
                ct[i]--;
                break;
            }
        }
        sum+=ct[i];
    }
    ct[s-1] = n-sum;
    for (int i =0; i < s; i++){
        pq.push_back(string(ct[i],(char)(i+'a')));
        //printf("%d ",ct[i]);
    }
    sort(pq.begin(),pq.end(),cmp);
    while (pq.size() != 1){
        string s = pq.back(); pq.pop_back();
        string t = pq.back(); pq.pop_back();
        pq.push_back(merge(s,t));
        sort(pq.begin(),pq.end(),cmp);
    }
    return pq[0];
}

Compilation message (stderr)

password.cpp: In function 'bool query()':
password.cpp:12:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     return query(str) == str.size();
            ~~~~~~~~~~~^~~~~~~~~~~~~
password.cpp: In function 'std::__cxx11::string merge(std::__cxx11::string, std::__cxx11::string)':
password.cpp:18:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (s.size() == 0 || query(test) != t.size()+1){
                          ~~~~~~~~~~~~^~~~~~~~~~~~~

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