oj.uz

Submission #557468

# Submission time Handle Problem Language Result Execution time Memory
557468 2022-05-05T10:46:20 Z FatihSolak Password (RMI18_password) C++17
50 / 100
 501 ms 36256 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 += a + 'a';
    for(int i = 0;i<d;i++)
        tmp += b + 'a';
    return rem[a][b][c] = myquery(tmp);
}
int ask2(int a,int b,int c,int d){
    return rem[a][b][c];
}
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);
    }
    vector<int> cnt(s);
    vector<int> used(s);
    vector<int> init(s);
    for(int i = 0;i<s;i++){
        cnt[v[i]] = ask(v[i],0,n,0);
        init[v[i]] = cnt[v[i]];
    }
    string res = "";
    for(int x = n-1;x>=0;x--){
        vector<bool> ok(s);
        for(int i = 0;i<s;i++){
            for(int j = 0;j<s;j++){
                if(i == j)continue;
                if(ask2(v[i],v[j],cnt[v[i]],init[v[j]]) >= cnt[v[i]] + used[v[j]] + 1){
                    ok[i] = 1;
                }
            }
        }
        int val = 0;
        while(cnt[v[val]] == 0 || ok[val])
            val++;
        for(int i = val+1;i<s;i++){
            if(cnt[v[i]] == 0 || ok[i])continue;
            if(ask(v[val],v[i],cnt[v[val]],init[v[i]]) >= cnt[v[val]] + used[v[i]] + 1){
                val = i;
            }
        }
        res += v[val] + 'a';
        used[v[val]]++;
        cnt[v[val]]--;
    }
    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 90 queries.
2 Correct 12 ms 17872 KB Guessed the password with 153 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17928 KB Guessed the password with 27 queries.
2 Correct 9 ms 17872 KB Guessed the password with 90 queries.
3 Correct 8 ms 17812 KB Guessed the password with 17 queries.
4 Correct 9 ms 17872 KB Guessed the password with 118 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 17920 KB Guessed the password with 2860 queries.
2 Correct 81 ms 17920 KB Guessed the password with 8067 queries.
3 Correct 93 ms 17932 KB Guessed the password with 7089 queries.
4 Correct 162 ms 17924 KB Guessed the password with 14793 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17872 KB Guessed the password with 90 queries.
2 Correct 12 ms 17872 KB Guessed the password with 153 queries.
3 Correct 10 ms 17928 KB Guessed the password with 27 queries.
4 Correct 9 ms 17872 KB Guessed the password with 90 queries.
5 Correct 8 ms 17812 KB Guessed the password with 17 queries.
6 Correct 9 ms 17872 KB Guessed the password with 118 queries.
7 Correct 31 ms 17920 KB Guessed the password with 2860 queries.
8 Correct 81 ms 17920 KB Guessed the password with 8067 queries.
9 Correct 93 ms 17932 KB Guessed the password with 7089 queries.
10 Correct 162 ms 17924 KB Guessed the password with 14793 queries.
11 Correct 375 ms 17952 KB Guessed the password with 32692 queries.
12 Correct 85 ms 17952 KB Guessed the password with 5878 queries.
13 Correct 358 ms 17932 KB Guessed the password with 38943 queries.
14 Correct 171 ms 18056 KB Guessed the password with 12895 queries.
15 Correct 348 ms 18060 KB Guessed the password with 29630 queries.
16 Correct 133 ms 17996 KB Guessed the password with 10301 queries.
17 Runtime error 501 ms 36256 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 9 ms 17872 KB Guessed the password with 90 queries.
2 Correct 12 ms 17872 KB Guessed the password with 153 queries.
3 Correct 10 ms 17928 KB Guessed the password with 27 queries.
4 Correct 9 ms 17872 KB Guessed the password with 90 queries.
5 Correct 8 ms 17812 KB Guessed the password with 17 queries.
6 Correct 9 ms 17872 KB Guessed the password with 118 queries.
7 Correct 31 ms 17920 KB Guessed the password with 2860 queries.
8 Correct 81 ms 17920 KB Guessed the password with 8067 queries.
9 Correct 93 ms 17932 KB Guessed the password with 7089 queries.
10 Correct 162 ms 17924 KB Guessed the password with 14793 queries.
11 Correct 375 ms 17952 KB Guessed the password with 32692 queries.
12 Correct 85 ms 17952 KB Guessed the password with 5878 queries.
13 Correct 358 ms 17932 KB Guessed the password with 38943 queries.
14 Correct 171 ms 18056 KB Guessed the password with 12895 queries.
15 Correct 348 ms 18060 KB Guessed the password with 29630 queries.
16 Correct 133 ms 17996 KB Guessed the password with 10301 queries.
17 Runtime error 501 ms 36256 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -