oj.uz

Submission #557393

# Submission time Handle Problem Language Result Execution time Memory
557393 2022-05-05T09:06:48 Z FatihSolak Password (RMI18_password) C++17
50 / 100
 1392 ms 17956 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] = 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 9 ms 17872 KB Guessed the password with 27 queries.
2 Correct 9 ms 17928 KB Guessed the password with 103 queries.
3 Correct 8 ms 17908 KB Guessed the password with 17 queries.
4 Correct 10 ms 17844 KB Guessed the password with 133 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 17872 KB Guessed the password with 3770 queries.
2 Correct 158 ms 17920 KB Guessed the password with 9261 queries.
3 Correct 153 ms 17920 KB Guessed the password with 9839 queries.
4 Correct 340 ms 17956 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 9 ms 17872 KB Guessed the password with 27 queries.
4 Correct 9 ms 17928 KB Guessed the password with 103 queries.
5 Correct 8 ms 17908 KB Guessed the password with 17 queries.
6 Correct 10 ms 17844 KB Guessed the password with 133 queries.
7 Correct 67 ms 17872 KB Guessed the password with 3770 queries.
8 Correct 158 ms 17920 KB Guessed the password with 9261 queries.
9 Correct 153 ms 17920 KB Guessed the password with 9839 queries.
10 Correct 340 ms 17956 KB Guessed the password with 18313 queries.
11 Correct 787 ms 17928 KB Guessed the password with 33171 queries.
12 Correct 249 ms 17920 KB Guessed the password with 9059 queries.
13 Correct 1252 ms 17924 KB Guessed the password with 46117 queries.
14 Correct 515 ms 17928 KB Guessed the password with 17880 queries.
15 Correct 1268 ms 17872 KB Guessed the password with 43506 queries.
16 Correct 486 ms 17832 KB Guessed the password with 16258 queries.
17 Execution timed out 1392 ms 17928 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 9 ms 17872 KB Guessed the password with 27 queries.
4 Correct 9 ms 17928 KB Guessed the password with 103 queries.
5 Correct 8 ms 17908 KB Guessed the password with 17 queries.
6 Correct 10 ms 17844 KB Guessed the password with 133 queries.
7 Correct 67 ms 17872 KB Guessed the password with 3770 queries.
8 Correct 158 ms 17920 KB Guessed the password with 9261 queries.
9 Correct 153 ms 17920 KB Guessed the password with 9839 queries.
10 Correct 340 ms 17956 KB Guessed the password with 18313 queries.
11 Correct 787 ms 17928 KB Guessed the password with 33171 queries.
12 Correct 249 ms 17920 KB Guessed the password with 9059 queries.
13 Correct 1252 ms 17924 KB Guessed the password with 46117 queries.
14 Correct 515 ms 17928 KB Guessed the password with 17880 queries.
15 Correct 1268 ms 17872 KB Guessed the password with 43506 queries.
16 Correct 486 ms 17832 KB Guessed the password with 16258 queries.
17 Execution timed out 1392 ms 17928 KB Time limit exceeded (wall clock)
18 Halted 0 ms 0 KB -