Submission #199700

#	Time	Username	Problem	Language	Result	Execution time	Memory
199700		mohamedsobhi777	Password (RMI18_password)	C++17	100 / 100	361 ms	784 KiB

password

#include <bits/stdc++.h>
using namespace std;

int N = 2000;
vector<int> acc(26 , 0);
int query(string s);

string merg(string aa , string bb)
{
    int s1 = aa.size();
    int s2 = bb.size();
    string ret = aa;
    int j = s2-1;
    for(int i = s1;i>=0&&j>=0;i--)
    {
        string tmp ;
        bool ok = 1;
        while(ok && j>=0)
        {
            tmp = ret.substr(0 , i) + bb[j];
            tmp+=ret.substr( i , s1 - i );
            if(query(tmp)==tmp.size())
            {
                ret = tmp;
                s1++;
                j--;
            }else ok = 0;
        }
    }
    return ret ;
}
int l[550] , r[550];

string build(int i)
{
    if(l[i] ==r[i] && r[i] ==-1 )
        return string( acc[i] , char('a' + i));
    string s1 = "";
    string s2 = "";
    if(l[i]!=-1)
        s1 = build(l[i] );
    if(r[i]!=-1)
        s2 = build(r[i] );
    string ret = merg(s1 , s2);
    return ret;

}
int t = 1;

string guess(int n, int s)
{
    memset(l , -1 , sizeof l);
    memset(r , -1 , sizeof r);
    int sum = 0;
    for(int i = 'a';i<'a' + s -1 ;i++)
    {
        acc[i-'a'] = query(string(n , char(i)));
        sum+=acc[i-'a'];
    }
    acc[s - 1] =  n  - sum;
    //hUFFMAN CODING
    priority_queue<pair<int , int> > q;

    for(int i= 0;i<s;i++)
        if(acc[i])
            q.push({ -acc[i] , i });
    t = s+1;
    while(q.size() > 1)
    {
        pair<int ,int > tp1 = q.top();q.pop();
        pair<int ,int > tp2 = q.top();q.pop();
        int sum = tp1.first+tp2.first;
        l[t] = tp1.second;
        r[t] = tp2.second;
        q.push({sum , t++});
    }
    return build(q.top().second);
}

Compilation message (stderr)

password.cpp: In function 'std::__cxx11::string merg(std::__cxx11::string, std::__cxx11::string)':
password.cpp:22:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(query(tmp)==tmp.size())
                ~~~~~~~~~~^~~~~~~~~~~~

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