Submission #1241253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241253		Hanksburger	Password (RMI18_password)	C++20	0 / 100	17 ms	432 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(0);
    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++)
    {
        //cout << "i=" << i << '\n';
        int pre=-1;
        for (int j=1; j<=vec[i].first; j++)
        {
            //cout << "j=" << j << '\n';
            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);
            int l=max(pre, findKth(cur, 'a'+vec[0].second, res))+1;
            int r=findKth(cur, 'a'+vec[0].second, res+1);
            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);
                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;
            //cout << "Cur " << cur << '\n';
        }
    }
    return cur;
}

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