Submission #1093850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093850		DobromirAngelov	Password (RMI18_password)	C++14	100 / 100	201 ms	1340 KiB

password

#include<bits/stdc++.h>
 
using namespace std;
 
int query(string str);
 
vector<string> seq;
priority_queue<pair<int,int> > pq;

int mergeQuery(int ind1,int len,string last)
{
    string str=seq[ind1].substr(0,len);
    reverse(last.begin(), last.end());
    str+=last;
    return query(str);
}
 
void mergeSeq(int ind1,int ind2)
{
    string ret="";
    int ptr=(int)seq[ind2].size()-1;
    for(int i=(int)seq[ind1].size()-1;i>=0;i--)
    {
        while(1)
        {
            if(ptr<0) break;
            ret+=seq[ind2][ptr];
            int cnt=mergeQuery(ind1,i+1,ret);
            if(cnt!=(i+1+(int)ret.size()))
            {
                ret.pop_back();
                break;
            }
            else ptr--;
        }
        ret+=seq[ind1][i];
    }
    for(int i=ptr;i>=0;i--) ret+=seq[ind2][i];
    reverse(ret.begin(), ret.end());
    seq[ind1]=ret;
}
 
string guess(int n,int s)
{
    for(int i=0;i<s;i++)
    {
        string str=string(n,(char)(i+'a'));
        int cnt=query(str);
        if(cnt>0)
        {
            string cur=string(cnt,(char)(i+'a'));
            seq.push_back(cur);
        }
    }
 
    for(int i=0;i<seq.size();i++)
    {
        pq.push({-((int)seq[i].size()), i});
    }
 
    while(pq.size()>1)
    {
        int ind1=pq.top().second;
        pq.pop();
        int ind2=pq.top().second;
        pq.pop();
        pq.push({-((int)seq[ind1].size()+(int)seq[ind2].size()),ind1});
        mergeSeq(ind1,ind2);
    }
 
    int ind=pq.top().second;
    return seq[ind];
}

Compilation message (stderr)

password.cpp: In function 'std::string guess(int, int)':
password.cpp:56:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i=0;i<seq.size();i++)
      |                 ~^~~~~~~~~~~

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