Submission #1034781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034781		andrei_iorgulescu	Password (RMI18_password)	C++14	100 / 100	139 ms	1100 KiB

password

#include <bits/stdc++.h>
 
using namespace std;
 
int query(string s);
 
string ans;
int S;
int N;
int fr_glob[30];
 
void solve(int l, int r, vector <int> fr, vector<int> bef,
           vector <int> aft)
{
    if (l > r)
        return;
    int ct = 0,cn;
    for (int i = 0; i < S; i++)
        if (fr[i] != 0)
            ct++,cn = i;
    if (ct == 1)
    {
        for (int i = l; i <= r; i++)
            ans[i] = (char)('a' + cn);
        return;
    }
    vector<pair<int,int>> cine;
    for (int i = 0; i < S; i++)
        for (int j = 0; j < fr[i]; j++)
            cine.push_back({i,j});
    int pivot = rand() % (int)cine.size();
    //cout << cine[pivot].first << ' ' << cine[pivot].second << endl;
    string def_l;
    if (l != 0)
    {
        int cr = ans[l - 1] - 'a', cate = bef[cr];
        for (int i = 1; i <= cate; i++)
            def_l.push_back(ans[l - 1]);
    }
    for (int i = 0; i <= cine[pivot].second; i++)
        def_l.push_back((char)('a' + cine[pivot].first));
    vector<int> frl(S), frr(S);
    for (int i = 0; i < S; i++)
    {
        if (i != cine[pivot].first and fr[i] > 0)
        {
            string to_query = def_l;
            for (int j = 0; j < fr[i] + aft[i]; j++)
                to_query.push_back((char)('a' + i));
            int qr = query(to_query);
            frr[i] = qr - (int)def_l.size() - aft[i];
            frl[i] = fr[i] - frr[i];
        }
        else if (i == cine[pivot].first)
        {
            frl[i] = cine[pivot].second;
            frr[i] = fr[i] - frl[i] - 1;
        }
    }
    int posi = l;
    for (int i = 0; i < S; i++)
        posi += frl[i];
    ans[posi] = (char)('a' + cine[pivot].first);
    vector<int> bef_new(S), aft_new(S);
    for (int i = 0; i < S; i++)
        bef_new[i] = bef[i] + frl[i];
    for (int i = 0; i < S; i++)
        aft_new[i] = aft[i] + frr[i];
    bef_new[cine[pivot].first]++;
    aft_new[cine[pivot].first]++;
    solve(l,posi - 1,frl,bef,aft_new);
    solve(posi + 1,r,frr,bef_new,aft);
}
 
string guess(int n, int s)
{
    srand(34567);
    N = n;
    S = s;
    ans.resize(n);
    vector<int> fr(s);
    for (int i = 0; i < s; i++)
    {
        string l;
        for (int j = 0; j < n; j++)
            l.push_back((char)('a' + i));
        fr[i] = query(l);
        fr_glob[i] = fr[i];
    }
    vector<int> vgol(s);
    solve(0,n - 1,fr,vgol,vgol);
    return ans;
}

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