Submission #248815

#	Time	Username	Problem	Language	Result	Execution time	Memory
248815		tqbfjotld	Password (RMI18_password)	C++14	100 / 100	971 ms	824 KiB

password

#include <bits/stdc++.h>
using namespace std;
int query(string str);

///editorial solution, based on quicksort?, s+n+nlogs supposedly
char ans[5005];
int N;
int tot_occ[128];

string repeat(char c, int n){
    string ret = "";
    for (int x = 0; x<n; x++){
        ret+=c;
    }
    return ret;
}

void rec(int l,int r,vector<pair<char,int> > chars){
    ///assume all subproblems to the left have been solved

    ///base case
    if (chars.size()==0) return;
    if (chars.size()==1){
            for (int x = l; x<l+chars[0].second; x++){
                ans[x] = chars[0].first;
            }
            return;
    }


    ///randomly choose pivot
    int pos = rand()%(r-l+1);

    int occ = 0; ///occ-th occurrence of the character (0-index)
    char ch;
    int totalch;
    for (auto x : chars){
        if (x.second>pos){
            occ = pos;
            ch = x.first;
            totalch = x.second;
            break;
        }
        pos -= x.second;
    }
    int occbef = 0; ///occurrences to the left of the subproblem
    for (int x = 0; x<l; x++){
        if (ans[x]==ch){
            occbef++;
        }
    }

    vector<pair<char,int> > lch,rch;
    for (auto x : chars){
        if (x.first==ch) continue;
        string qu = repeat(ch,occbef+occ+1);
        qu += repeat(x.first,N-qu.size());
        int res = query(qu);
        res -= occbef+occ+1;
        res = tot_occ[x.first]-res;
        for (int y = 0; y<l; y++){
            if (ans[y]==x.first) res--;
        }
        if (res>0){
            lch.push_back({x.first,res});
        }
        if (x.second-res>0){
            rch.push_back({x.first,x.second-res});
        }
    }
    if (occ>0){
        lch.push_back({ch,occ});
    }
    if (totalch-occ-1>0){
        rch.push_back({ch,totalch-occ-1});
    }
    int offset = 0;
    for (auto x : lch){
        offset += x.second;
    }
    rec(l,l+offset-1,lch);
    ans[l+offset] = ch;
    rec(l+offset+1,r,rch);
    return;

}

string guess(int n, int s){
    vector<pair<char,int> > chars;
    N = n;
    for (int x = 0; x<s; x++){
        string qu = repeat('a'+x,n);
        int t = query(qu);
        if (t>0){
            chars.push_back({'a'+x,t});
        }
        tot_occ['a'+x] = t;
    }
    rec(0,n-1,chars);
    string Ans = "";
    for (int x = 0; x<n; x++){
        Ans += ans[x];
    }
    return Ans;
}

Compilation message (stderr)

password.cpp: In function 'void rec(int, int, std::vector<std::pair<char, int> >)':
password.cpp:61:30: warning: array subscript has type 'char' [-Wchar-subscripts]
         res = tot_occ[x.first]-res;
                              ^
password.cpp:75:5: warning: 'totalch' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if (totalch-occ-1>0){
     ^~
password.cpp:57:43: warning: 'ch' may be used uninitialized in this function [-Wmaybe-uninitialized]
         string qu = repeat(ch,occbef+occ+1);
                                           ^

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