Submission #709396

#	Time	Username	Problem	Language	Result	Execution time	Memory
709396		beepbeepsheep	Password (RMI18_password)	C++17	100 / 100	252 ms	752 KiB

password

#include <bits/stdc++.h>
using namespace std;
int arr[26];
int query(string s);
string build(string &s, char c, int pos){
    string ret="";
    for (int i=0;i<pos;i++){
        ret+=s[i];
    }
    ret+=c;
    for (int i=pos;i<s.size();i++){
        ret+=s[i];
    }
    return ret;
}
string mrg(string a, string b){
    int lptr=0,rptr=0;
    string ans="";
    while (lptr<a.size() && rptr<b.size()){
        string test=ans+a[lptr]+b.substr(rptr);
        if (query(test)==test.length()){
            ans+=a[lptr];
            lptr++;
        } else{
            ans+=b[rptr];
            rptr++;
        }
    }
    while (lptr<a.size()){
        ans+=a[lptr];
        lptr++;
    }
    while (rptr<b.size()){
        ans+=b[rptr];
        rptr++;
    }
    return ans;
}
string dup(char c, int n){
    string ret="";
    for (int i=0;i<n;i++) ret+=c;
    return ret;
}
priority_queue<pair<int,string>> pq;
string guess(int n, int s){
    for (int i=0;i<s;i++){
        arr[i]=query(dup(i+'a',n));
        if (arr[i]==0) continue;
        pq.emplace(-arr[i],dup(i+'a',arr[i]));
    }
    while (pq.size()>1){
        string a=pq.top().second;
        pq.pop();
        string b=pq.top().second;
        pq.pop();
        string ans=mrg(a,b);
        pq.emplace(-ans.length(),ans);
    }
    return pq.top().second;
}

Compilation message (stderr)

password.cpp: In function 'std::string build(std::string&, char, int)':
password.cpp:11:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for (int i=pos;i<s.size();i++){
      |                    ~^~~~~~~~~
password.cpp: In function 'std::string mrg(std::string, std::string)':
password.cpp:19:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     while (lptr<a.size() && rptr<b.size()){
      |            ~~~~^~~~~~~~~
password.cpp:19:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     while (lptr<a.size() && rptr<b.size()){
      |                             ~~~~^~~~~~~~~
password.cpp:21:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         if (query(test)==test.length()){
      |             ~~~~~~~~~~~^~~~~~~~~~~~~~~
password.cpp:29:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     while (lptr<a.size()){
      |            ~~~~^~~~~~~~~
password.cpp:33:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     while (rptr<b.size()){
      |            ~~~~^~~~~~~~~

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