Submission #1241271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241271		Hanksburger	Password (RMI18_password)	C++20	0 / 100	8 ms	428 KiB

password

#include <bits/stdc++.h>
using namespace std;
int query(string str);
int findKth(string str, char c, int k)
{
    if (!k)
        return -1;
    int cnt=0;
    for (int i=0; i<str.length(); i++)
    {
        if (str[i]==c)
            cnt++;
        if (cnt==k)
            return i;
    }
    return str.length();
}
string guess(int N, int S)
{
    vector<pair<int, int> > vec;
    int freq[30];
    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++)
    {
        int pre=-1;
        for (int j=1; j<=vec[i].first; j++)
        {
            int l=pre+1, r=cur.length();
            while (l<r)
            {
                int mid=(l+r)/2;
                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(cur[mid]);
                int res=freq[cur[mid]-'a']-(query(tmp)-j);
                l=max(l, findKth(cur, cur[mid], res)+1);
                r=min(r, findKth(cur, cur[mid], res+1));
            }
            cur.insert(cur.begin()+l, 'a'+vec[i].second);
            pre=l;
        }
    }
    return cur;
}

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