Submission #557389

#	Time	Username	Problem	Language	Result	Execution time	Memory
557389		FatihSolak	Password (RMI18_password)	C++17	50 / 100	1411 ms	18000 KiB

password

#include <bits/stdc++.h>
using namespace std;
int query(string str);
// string password;
// int query(string q) {
//   int len = q.size();
//   int i = 0, j = 0, plen = password.size();
//   while (i < plen && j < len) {
//     while ((i < plen) && (password[i] != q[j])) {
//       i++;
//     }
//     if (i < plen) {
//       i++;
//       j++;
//     }
//   }
//   return j;
// }
int rem[30][30][5005];
int ask(int a,int b,int c,int d){
    if(rem[a][b][c]  != -1)return rem[a][b][c];
    string tmp = "";
    for(int i = 0;i<c;i++)
        tmp += (char)(a + 'a');
    for(int i = 0;i<d;i++)
        tmp += (char)(b + 'a');
    return rem[a][b][c] = query(tmp);
}
string guess(int n, int s){
    for(int i = 0;i<30;i++){
        for(int j = 0;j<30;j++){
            for(int c = 0;c<5005;c++){
                rem[i][j][c] = -1;
            }
        }
    }
    vector<int> cnt(s);
    vector<int> used(s);
    for(int i = 0;i<s;i++){
        string tmp = "";
        for(int j = 0;j<n;j++)
            tmp += (char) (i + 'a');
        //cout << tmp << endl;
        cnt[i] = query(tmp);
    }
    string res = "";
    for(int x = n-1;x>=0;x--){
        int val = 0;
        while(cnt[val] == 0)
            val++;
        for(int i = val+1;i<s;i++){
            if(cnt[i] == 0)continue;
            if(ask(val,i,cnt[val],n-cnt[val]) >= cnt[val] + used[i] + 1){
                val = i;
            }
        }
        res += (char)(val + 'a');
        used[val]++;
        cnt[val]--;
        //cout << res << endl;
    }
    reverse(res.begin(),res.end());
    return res;
}
// int main(){
//     #ifdef Local
//         freopen("in.txt","r",stdin);
//         freopen("out.txt","w",stdout);
//     #endif
//     int n,s;
//     cin >> n >> s;
//     cin >> password;
//     guess(n,s);
// }

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