oj.uz

Submission #557389

# Submission time Handle Problem Language Result Execution time Memory
557389 2022-05-05T09:04:36 Z FatihSolak Password (RMI18_password) C++17
50 / 100
 1411 ms 18000 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 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.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 17872 KB Guessed the password with 27 queries.
2 Correct 8 ms 17872 KB Guessed the password with 103 queries.
3 Correct 8 ms 17872 KB Guessed the password with 17 queries.
4 Correct 11 ms 17872 KB Guessed the password with 133 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 17840 KB Guessed the password with 3770 queries.
2 Correct 134 ms 18000 KB Guessed the password with 9261 queries.
3 Correct 192 ms 17924 KB Guessed the password with 9839 queries.
4 Correct 318 ms 17936 KB Guessed the password with 18313 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17872 KB Guessed the password with 86 queries.
2 Correct 9 ms 17872 KB Guessed the password with 154 queries.
3 Correct 7 ms 17872 KB Guessed the password with 27 queries.
4 Correct 8 ms 17872 KB Guessed the password with 103 queries.
5 Correct 8 ms 17872 KB Guessed the password with 17 queries.
6 Correct 11 ms 17872 KB Guessed the password with 133 queries.
7 Correct 71 ms 17840 KB Guessed the password with 3770 queries.
8 Correct 134 ms 18000 KB Guessed the password with 9261 queries.
9 Correct 192 ms 17924 KB Guessed the password with 9839 queries.
10 Correct 318 ms 17936 KB Guessed the password with 18313 queries.
11 Correct 820 ms 17928 KB Guessed the password with 33171 queries.
12 Correct 242 ms 17924 KB Guessed the password with 9059 queries.
13 Correct 1187 ms 17972 KB Guessed the password with 46117 queries.
14 Correct 508 ms 17920 KB Guessed the password with 17880 queries.
15 Correct 1124 ms 17872 KB Guessed the password with 43506 queries.
16 Correct 448 ms 17872 KB Guessed the password with 16258 queries.
17 Execution timed out 1411 ms 17924 KB Time limit exceeded (wall clock)
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17872 KB Guessed the password with 86 queries.
2 Correct 9 ms 17872 KB Guessed the password with 154 queries.
3 Correct 7 ms 17872 KB Guessed the password with 27 queries.
4 Correct 8 ms 17872 KB Guessed the password with 103 queries.
5 Correct 8 ms 17872 KB Guessed the password with 17 queries.
6 Correct 11 ms 17872 KB Guessed the password with 133 queries.
7 Correct 71 ms 17840 KB Guessed the password with 3770 queries.
8 Correct 134 ms 18000 KB Guessed the password with 9261 queries.
9 Correct 192 ms 17924 KB Guessed the password with 9839 queries.
10 Correct 318 ms 17936 KB Guessed the password with 18313 queries.
11 Correct 820 ms 17928 KB Guessed the password with 33171 queries.
12 Correct 242 ms 17924 KB Guessed the password with 9059 queries.
13 Correct 1187 ms 17972 KB Guessed the password with 46117 queries.
14 Correct 508 ms 17920 KB Guessed the password with 17880 queries.
15 Correct 1124 ms 17872 KB Guessed the password with 43506 queries.
16 Correct 448 ms 17872 KB Guessed the password with 16258 queries.
17 Execution timed out 1411 ms 17924 KB Time limit exceeded (wall clock)
18 Halted 0 ms 0 KB -