oj.uz

Submission #557399

# Submission time Handle Problem Language Result Execution time Memory
557399 2022-05-05T09:14:21 Z FatihSolak Password (RMI18_password) C++17
80 / 100
 1410 ms 18220 KB 
#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 tot = 50000;
int myquery(string s){
    assert(tot--);
    return query(s);
}
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] = myquery(tmp);
}
mt19937 rng(58);
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> v;
    for(int i = 0;i<s;i++){
        v.push_back(i);
    }
    shuffle(v.begin(),v.end(),rng);
    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) (v[i] + 'a');
        //cout << tmp << endl;
        cnt[i] = myquery(tmp);
        //cout << cnt[i] << endl;
    }
    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(v[val],v[i],cnt[val],n-cnt[val]) >= cnt[val] + used[i] + 1){
                val = i;
            }
        }
        res += (char)(v[val] + 'a');
        used[val]++;
        cnt[val]--;
        //cout << val << endl;
        //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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17872 KB Guessed the password with 76 queries.
2 Correct 9 ms 17872 KB Guessed the password with 181 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17872 KB Guessed the password with 25 queries.
2 Correct 8 ms 17872 KB Guessed the password with 63 queries.
3 Correct 8 ms 17896 KB Guessed the password with 18 queries.
4 Correct 10 ms 17872 KB Guessed the password with 186 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 17924 KB Guessed the password with 4774 queries.
2 Correct 111 ms 17924 KB Guessed the password with 8693 queries.
3 Correct 100 ms 17872 KB Guessed the password with 5595 queries.
4 Correct 380 ms 17928 KB Guessed the password with 18801 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17872 KB Guessed the password with 76 queries.
2 Correct 9 ms 17872 KB Guessed the password with 181 queries.
3 Correct 8 ms 17872 KB Guessed the password with 25 queries.
4 Correct 8 ms 17872 KB Guessed the password with 63 queries.
5 Correct 8 ms 17896 KB Guessed the password with 18 queries.
6 Correct 10 ms 17872 KB Guessed the password with 186 queries.
7 Correct 67 ms 17924 KB Guessed the password with 4774 queries.
8 Correct 111 ms 17924 KB Guessed the password with 8693 queries.
9 Correct 100 ms 17872 KB Guessed the password with 5595 queries.
10 Correct 380 ms 17928 KB Guessed the password with 18801 queries.
11 Correct 596 ms 17992 KB Guessed the password with 24561 queries.
12 Correct 558 ms 17992 KB Guessed the password with 25707 queries.
13 Correct 895 ms 17928 KB Guessed the password with 37815 queries.
14 Correct 798 ms 18000 KB Guessed the password with 33822 queries.
15 Correct 1067 ms 17932 KB Guessed the password with 41569 queries.
16 Correct 886 ms 17932 KB Guessed the password with 35707 queries.
17 Correct 921 ms 17932 KB Guessed the password with 35567 queries.
18 Correct 808 ms 17928 KB Guessed the password with 30991 queries.
19 Correct 911 ms 17924 KB Guessed the password with 33336 queries.
20 Correct 963 ms 17872 KB Guessed the password with 35555 queries.
21 Correct 1010 ms 17872 KB Guessed the password with 35443 queries.
22 Correct 1171 ms 17872 KB Guessed the password with 44118 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17872 KB Guessed the password with 76 queries.
2 Correct 9 ms 17872 KB Guessed the password with 181 queries.
3 Correct 8 ms 17872 KB Guessed the password with 25 queries.
4 Correct 8 ms 17872 KB Guessed the password with 63 queries.
5 Correct 8 ms 17896 KB Guessed the password with 18 queries.
6 Correct 10 ms 17872 KB Guessed the password with 186 queries.
7 Correct 67 ms 17924 KB Guessed the password with 4774 queries.
8 Correct 111 ms 17924 KB Guessed the password with 8693 queries.
9 Correct 100 ms 17872 KB Guessed the password with 5595 queries.
10 Correct 380 ms 17928 KB Guessed the password with 18801 queries.
11 Correct 596 ms 17992 KB Guessed the password with 24561 queries.
12 Correct 558 ms 17992 KB Guessed the password with 25707 queries.
13 Correct 895 ms 17928 KB Guessed the password with 37815 queries.
14 Correct 798 ms 18000 KB Guessed the password with 33822 queries.
15 Correct 1067 ms 17932 KB Guessed the password with 41569 queries.
16 Correct 886 ms 17932 KB Guessed the password with 35707 queries.
17 Correct 921 ms 17932 KB Guessed the password with 35567 queries.
18 Correct 808 ms 17928 KB Guessed the password with 30991 queries.
19 Correct 911 ms 17924 KB Guessed the password with 33336 queries.
20 Correct 963 ms 17872 KB Guessed the password with 35555 queries.
21 Correct 1010 ms 17872 KB Guessed the password with 35443 queries.
22 Correct 1171 ms 17872 KB Guessed the password with 44118 queries.
23 Execution timed out 1410 ms 18220 KB Time limit exceeded (wall clock)
24 Halted 0 ms 0 KB -