oj.uz

Submission #557395

# Submission time Handle Problem Language Result Execution time Memory
557395 2022-05-05T09:07:05 Z FatihSolak Password (RMI18_password) C++17
50 / 100
 1278 ms 36236 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);
}
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] = myquery(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 10 ms 17872 KB Guessed the password with 86 queries.
2 Correct 9 ms 17916 KB Guessed the password with 154 queries.

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 17916 KB Guessed the password with 3770 queries.
2 Correct 151 ms 17916 KB Guessed the password with 9261 queries.
3 Correct 196 ms 17944 KB Guessed the password with 9839 queries.
4 Correct 414 ms 17920 KB Guessed the password with 18313 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17872 KB Guessed the password with 86 queries.
2 Correct 9 ms 17916 KB Guessed the password with 154 queries.
3 Correct 10 ms 17848 KB Guessed the password with 27 queries.
4 Correct 12 ms 17872 KB Guessed the password with 103 queries.
5 Correct 12 ms 17872 KB Guessed the password with 17 queries.
6 Correct 11 ms 17856 KB Guessed the password with 133 queries.
7 Correct 70 ms 17916 KB Guessed the password with 3770 queries.
8 Correct 151 ms 17916 KB Guessed the password with 9261 queries.
9 Correct 196 ms 17944 KB Guessed the password with 9839 queries.
10 Correct 414 ms 17920 KB Guessed the password with 18313 queries.
11 Correct 885 ms 17928 KB Guessed the password with 33171 queries.
12 Correct 258 ms 17928 KB Guessed the password with 9059 queries.
13 Correct 1278 ms 17928 KB Guessed the password with 46117 queries.
14 Correct 498 ms 17932 KB Guessed the password with 17880 queries.
15 Correct 1146 ms 17924 KB Guessed the password with 43506 queries.
16 Correct 450 ms 17924 KB Guessed the password with 16258 queries.
17 Runtime error 1166 ms 36236 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17872 KB Guessed the password with 86 queries.
2 Correct 9 ms 17916 KB Guessed the password with 154 queries.
3 Correct 10 ms 17848 KB Guessed the password with 27 queries.
4 Correct 12 ms 17872 KB Guessed the password with 103 queries.
5 Correct 12 ms 17872 KB Guessed the password with 17 queries.
6 Correct 11 ms 17856 KB Guessed the password with 133 queries.
7 Correct 70 ms 17916 KB Guessed the password with 3770 queries.
8 Correct 151 ms 17916 KB Guessed the password with 9261 queries.
9 Correct 196 ms 17944 KB Guessed the password with 9839 queries.
10 Correct 414 ms 17920 KB Guessed the password with 18313 queries.
11 Correct 885 ms 17928 KB Guessed the password with 33171 queries.
12 Correct 258 ms 17928 KB Guessed the password with 9059 queries.
13 Correct 1278 ms 17928 KB Guessed the password with 46117 queries.
14 Correct 498 ms 17932 KB Guessed the password with 17880 queries.
15 Correct 1146 ms 17924 KB Guessed the password with 43506 queries.
16 Correct 450 ms 17924 KB Guessed the password with 16258 queries.
17 Runtime error 1166 ms 36236 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -