oj.uz

Submission #557478

# Submission time Handle Problem Language Result Execution time Memory
557478 2022-05-05T11:01:09 Z FatihSolak Password (RMI18_password) C++17
50 / 100
 505 ms 36264 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];
}
mt19937 rng(31);
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;
                }
                if(ask2(v[i],v[j],cnt[v[i]],init[v[j]]) != -1 && ask2(v[i],v[j],cnt[v[i]],init[v[j]]) < cnt[v[i]] + used[v[j]] + 1){
                    ok[j] = 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] || cnt[v[val]] == x+1)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]]--;
        //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 86 queries.
2 Correct 8 ms 17872 KB Guessed the password with 154 queries.

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 17924 KB Guessed the password with 3770 queries.
2 Correct 79 ms 17924 KB Guessed the password with 9261 queries.
3 Correct 86 ms 17944 KB Guessed the password with 9839 queries.
4 Correct 179 ms 17872 KB Guessed the password with 18313 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17872 KB Guessed the password with 86 queries.
2 Correct 8 ms 17872 KB Guessed the password with 154 queries.
3 Correct 8 ms 17872 KB Guessed the password with 27 queries.
4 Correct 11 ms 17872 KB Guessed the password with 103 queries.
5 Correct 7 ms 17868 KB Guessed the password with 17 queries.
6 Correct 9 ms 17836 KB Guessed the password with 133 queries.
7 Correct 47 ms 17924 KB Guessed the password with 3770 queries.
8 Correct 79 ms 17924 KB Guessed the password with 9261 queries.
9 Correct 86 ms 17944 KB Guessed the password with 9839 queries.
10 Correct 179 ms 17872 KB Guessed the password with 18313 queries.
11 Correct 318 ms 17956 KB Guessed the password with 33171 queries.
12 Correct 107 ms 17956 KB Guessed the password with 9059 queries.
13 Correct 466 ms 18068 KB Guessed the password with 46117 queries.
14 Correct 213 ms 17948 KB Guessed the password with 17880 queries.
15 Correct 299 ms 17956 KB Guessed the password with 43506 queries.
16 Correct 154 ms 17952 KB Guessed the password with 16258 queries.
17 Runtime error 505 ms 36264 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 8 ms 17872 KB Guessed the password with 86 queries.
2 Correct 8 ms 17872 KB Guessed the password with 154 queries.
3 Correct 8 ms 17872 KB Guessed the password with 27 queries.
4 Correct 11 ms 17872 KB Guessed the password with 103 queries.
5 Correct 7 ms 17868 KB Guessed the password with 17 queries.
6 Correct 9 ms 17836 KB Guessed the password with 133 queries.
7 Correct 47 ms 17924 KB Guessed the password with 3770 queries.
8 Correct 79 ms 17924 KB Guessed the password with 9261 queries.
9 Correct 86 ms 17944 KB Guessed the password with 9839 queries.
10 Correct 179 ms 17872 KB Guessed the password with 18313 queries.
11 Correct 318 ms 17956 KB Guessed the password with 33171 queries.
12 Correct 107 ms 17956 KB Guessed the password with 9059 queries.
13 Correct 466 ms 18068 KB Guessed the password with 46117 queries.
14 Correct 213 ms 17948 KB Guessed the password with 17880 queries.
15 Correct 299 ms 17956 KB Guessed the password with 43506 queries.
16 Correct 154 ms 17952 KB Guessed the password with 16258 queries.
17 Runtime error 505 ms 36264 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -