Submission #519409

#	Time	Username	Problem	Language	Result	Execution time	Memory
519409		hohohaha	Password (RMI18_password)	C++14	100 / 100	263 ms	632 KiB

password

#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
 
//using namespace __gnu_pbds;
using namespace std;
 
typedef vector<int> vi;
 
string substr(string s, int l, int r) {
    string ans;
    for (int i = l; i <= r; i++)
        ans += s[i];
    return ans;
}
 
int query(string);
 
vi cnt;
 
string merge(string s,string t){
    if(s.size()<t.size())
        swap(s,t);
    for(int i=-1; i<int(s.size()); i++){
        if(!t.size())break;
        string cur=s.substr(0,i+1)+string(1,t[0])+s.substr(i+1,s.size()-(i+1));
        if(query(cur)==cur.size()){
            s=s.substr(0,i+1)+string(1,t[0])+s.substr(i+1,s.size()-(i+1));
            t=t.substr(1,t.size()-1);
        }
    }
    return s;
}
string dfs(int l,int r,int n){
    if(l>r)return "";
    else if(l==r)return string(cnt[l],l+'a');
 
    int m=(l+r)/2;
    return merge(dfs(l,m,n),dfs(m+1,r,n));
}
string guess(int n,int AB){
    cnt=vi(26);
    int sum=0;
    for(int i=0; i<AB; i++){
        int ans=query(string(n,i+'a'));
        cnt[i]=ans;
        sum+=ans;
    }
    return dfs(0,AB-1,n);
}

Compilation message (stderr)

password.cpp: In function 'std::string merge(std::string, std::string)':
password.cpp:27:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         if(query(cur)==cur.size()){
      |            ~~~~~~~~~~^~~~~~~~~~~~

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