oj.uz

Submission #557477

# Submission time Handle Problem Language Result Execution time Memory
557477 2022-05-05T11:00:06 Z FatihSolak Password (RMI18_password) C++17
100 / 100
 469 ms 18196 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);
    }
    //shuffle(v.begin(),v.end(),rng);
    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]]--;
        vector<int> tmp;
        for(int i = 0;i<val;i++){
            tmp.push_back(v[i]);
        }
        for(int i = val+1;i<v.size();i++){
            tmp.push_back(v[i]);
        }
        tmp.push_back(v[val]);
        v = tmp;
        //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);
// }

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:88:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         for(int i = val+1;i<v.size();i++){
      |                           ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 18000 KB Guessed the password with 86 queries.
2 Correct 9 ms 17924 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 23 queries.
2 Correct 8 ms 17872 KB Guessed the password with 43 queries.
3 Correct 8 ms 17872 KB Guessed the password with 9 queries.
4 Correct 9 ms 17872 KB Guessed the password with 100 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 17832 KB Guessed the password with 1566 queries.
2 Correct 28 ms 17872 KB Guessed the password with 1824 queries.
3 Correct 41 ms 17928 KB Guessed the password with 3834 queries.
4 Correct 82 ms 17932 KB Guessed the password with 6902 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 18000 KB Guessed the password with 86 queries.
2 Correct 9 ms 17924 KB Guessed the password with 154 queries.
3 Correct 9 ms 17872 KB Guessed the password with 23 queries.
4 Correct 8 ms 17872 KB Guessed the password with 43 queries.
5 Correct 8 ms 17872 KB Guessed the password with 9 queries.
6 Correct 9 ms 17872 KB Guessed the password with 100 queries.
7 Correct 25 ms 17832 KB Guessed the password with 1566 queries.
8 Correct 28 ms 17872 KB Guessed the password with 1824 queries.
9 Correct 41 ms 17928 KB Guessed the password with 3834 queries.
10 Correct 82 ms 17932 KB Guessed the password with 6902 queries.
11 Correct 100 ms 17948 KB Guessed the password with 6369 queries.
12 Correct 95 ms 17948 KB Guessed the password with 6460 queries.
13 Correct 115 ms 17948 KB Guessed the password with 9360 queries.
14 Correct 86 ms 18120 KB Guessed the password with 9036 queries.
15 Correct 99 ms 17948 KB Guessed the password with 9620 queries.
16 Correct 136 ms 17948 KB Guessed the password with 9659 queries.
17 Correct 108 ms 17872 KB Guessed the password with 7167 queries.
18 Correct 115 ms 18072 KB Guessed the password with 6716 queries.
19 Correct 120 ms 17956 KB Guessed the password with 7457 queries.
20 Correct 100 ms 17960 KB Guessed the password with 7753 queries.
21 Correct 53 ms 17952 KB Guessed the password with 2963 queries.
22 Correct 49 ms 17956 KB Guessed the password with 2730 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 18000 KB Guessed the password with 86 queries.
2 Correct 9 ms 17924 KB Guessed the password with 154 queries.
3 Correct 9 ms 17872 KB Guessed the password with 23 queries.
4 Correct 8 ms 17872 KB Guessed the password with 43 queries.
5 Correct 8 ms 17872 KB Guessed the password with 9 queries.
6 Correct 9 ms 17872 KB Guessed the password with 100 queries.
7 Correct 25 ms 17832 KB Guessed the password with 1566 queries.
8 Correct 28 ms 17872 KB Guessed the password with 1824 queries.
9 Correct 41 ms 17928 KB Guessed the password with 3834 queries.
10 Correct 82 ms 17932 KB Guessed the password with 6902 queries.
11 Correct 100 ms 17948 KB Guessed the password with 6369 queries.
12 Correct 95 ms 17948 KB Guessed the password with 6460 queries.
13 Correct 115 ms 17948 KB Guessed the password with 9360 queries.
14 Correct 86 ms 18120 KB Guessed the password with 9036 queries.
15 Correct 99 ms 17948 KB Guessed the password with 9620 queries.
16 Correct 136 ms 17948 KB Guessed the password with 9659 queries.
17 Correct 108 ms 17872 KB Guessed the password with 7167 queries.
18 Correct 115 ms 18072 KB Guessed the password with 6716 queries.
19 Correct 120 ms 17956 KB Guessed the password with 7457 queries.
20 Correct 100 ms 17960 KB Guessed the password with 7753 queries.
21 Correct 53 ms 17952 KB Guessed the password with 2963 queries.
22 Correct 49 ms 17956 KB Guessed the password with 2730 queries.
23 Correct 112 ms 17952 KB Guessed the password with 10323 queries.
24 Correct 102 ms 17952 KB Guessed the password with 5995 queries.
25 Correct 246 ms 18196 KB Guessed the password with 28063 queries.
26 Correct 149 ms 18076 KB Guessed the password with 14020 queries.
27 Correct 412 ms 17952 KB Guessed the password with 38404 queries.
28 Correct 170 ms 18024 KB Guessed the password with 13914 queries.
29 Correct 469 ms 17948 KB Guessed the password with 47266 queries.
30 Correct 178 ms 17960 KB Guessed the password with 11692 queries.