Submission #1241235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241235		Hanksburger	Password (RMI18_password)	C++20	0 / 100	12 ms	420 KiB

password

#include <bits/stdc++.h>
using namespace std;
int query(string s);
string guess(int N, int S)
{
    vector<pair<int, int> > vec;
    int freq[26];
    for (int i=0; i<S; i++)
    {
        string tmp;
        for (int j=0; j<N; j++)
            tmp.push_back('a'+i);
        freq[i]=query(tmp);
        vec.push_back({freq[i], i});
    }
    sort(vec.begin(), vec.end(), greater<pair<int, int> >());
    string cur;
    for (int j=0; j<vec[0].first; j++)
        cur.push_back('a'+vec[0].second);
    for (int i=1; i<vec.size(); i++)
    {
        for (int j=1; j<=vec[i].first; j++)
        {
            string tmp;
            for (int k=0; k<j; k++)
                tmp.push_back('a'+vec[i].second);
            for (int k=j; k<N; k++)
                tmp.push_back('a'+vec[0].second);
            int res=vec[0].first-(query(tmp)-j), cnt=0, l=-1, r;
            for (int k=0; k<=cur.length(); k++)
            {
                if (l==-1 && cnt==res)
                    l=k;
                if (k==cur.length() || cur[k]=='a'+vec[0].second)
                    cnt++;
                if (cnt==res+1)
                {
                    r=k;
                    break;
                }
            }
            while (l<r)
            {
                int mid=(l+r)/2;
                tmp.clear();
                for (int k=0; k<j; k++)
                    tmp.push_back('a'+vec[i].second);
                for (int k=j; k<N; k++)
                    tmp.push_back(cur[mid]);
                res=freq[cur[mid]-'a']-(query(tmp)-j), cnt=0;
                for (int k=0; k<=mid; k++)
                    if (cur[k]==cur[mid])
                        cnt++;
                if (res>=cnt)
                    l=mid+1;
                else
                    r=mid;
            }
            cur.insert(cur.begin()+l, 'a'+vec[i].second);
        }
    }
    return cur;
}

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