oj.uz

Submission #557462

# Submission time Handle Problem Language Result Execution time Memory
557462 2022-05-05T10:44:18 Z FatihSolak Password (RMI18_password) C++17
80 / 100
 497 ms 36144 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;
                }
            }
        }
        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]]--;
        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:85:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         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 17872 KB Guessed the password with 90 queries.
2 Correct 8 ms 17872 KB Guessed the password with 153 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 17872 KB Guessed the password with 23 queries.
2 Correct 8 ms 17832 KB Guessed the password with 43 queries.
3 Correct 9 ms 17872 KB Guessed the password with 9 queries.
4 Correct 9 ms 17872 KB Guessed the password with 110 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 18000 KB Guessed the password with 1792 queries.
2 Correct 27 ms 17888 KB Guessed the password with 1973 queries.
3 Correct 57 ms 17936 KB Guessed the password with 4460 queries.
4 Correct 77 ms 17928 KB Guessed the password with 8180 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17872 KB Guessed the password with 90 queries.
2 Correct 8 ms 17872 KB Guessed the password with 153 queries.
3 Correct 7 ms 17872 KB Guessed the password with 23 queries.
4 Correct 8 ms 17832 KB Guessed the password with 43 queries.
5 Correct 9 ms 17872 KB Guessed the password with 9 queries.
6 Correct 9 ms 17872 KB Guessed the password with 110 queries.
7 Correct 36 ms 18000 KB Guessed the password with 1792 queries.
8 Correct 27 ms 17888 KB Guessed the password with 1973 queries.
9 Correct 57 ms 17936 KB Guessed the password with 4460 queries.
10 Correct 77 ms 17928 KB Guessed the password with 8180 queries.
11 Correct 102 ms 17956 KB Guessed the password with 7478 queries.
12 Correct 118 ms 17960 KB Guessed the password with 7645 queries.
13 Correct 107 ms 17936 KB Guessed the password with 11340 queries.
14 Correct 132 ms 17932 KB Guessed the password with 10781 queries.
15 Correct 162 ms 17952 KB Guessed the password with 11735 queries.
16 Correct 156 ms 17952 KB Guessed the password with 11864 queries.
17 Correct 120 ms 17952 KB Guessed the password with 8411 queries.
18 Correct 106 ms 17956 KB Guessed the password with 7860 queries.
19 Correct 117 ms 18080 KB Guessed the password with 8738 queries.
20 Correct 133 ms 17956 KB Guessed the password with 9001 queries.
21 Correct 53 ms 17952 KB Guessed the password with 3190 queries.
22 Correct 55 ms 17928 KB Guessed the password with 2840 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17872 KB Guessed the password with 90 queries.
2 Correct 8 ms 17872 KB Guessed the password with 153 queries.
3 Correct 7 ms 17872 KB Guessed the password with 23 queries.
4 Correct 8 ms 17832 KB Guessed the password with 43 queries.
5 Correct 9 ms 17872 KB Guessed the password with 9 queries.
6 Correct 9 ms 17872 KB Guessed the password with 110 queries.
7 Correct 36 ms 18000 KB Guessed the password with 1792 queries.
8 Correct 27 ms 17888 KB Guessed the password with 1973 queries.
9 Correct 57 ms 17936 KB Guessed the password with 4460 queries.
10 Correct 77 ms 17928 KB Guessed the password with 8180 queries.
11 Correct 102 ms 17956 KB Guessed the password with 7478 queries.
12 Correct 118 ms 17960 KB Guessed the password with 7645 queries.
13 Correct 107 ms 17936 KB Guessed the password with 11340 queries.
14 Correct 132 ms 17932 KB Guessed the password with 10781 queries.
15 Correct 162 ms 17952 KB Guessed the password with 11735 queries.
16 Correct 156 ms 17952 KB Guessed the password with 11864 queries.
17 Correct 120 ms 17952 KB Guessed the password with 8411 queries.
18 Correct 106 ms 17956 KB Guessed the password with 7860 queries.
19 Correct 117 ms 18080 KB Guessed the password with 8738 queries.
20 Correct 133 ms 17956 KB Guessed the password with 9001 queries.
21 Correct 53 ms 17952 KB Guessed the password with 3190 queries.
22 Correct 55 ms 17928 KB Guessed the password with 2840 queries.
23 Correct 114 ms 17952 KB Guessed the password with 8445 queries.
24 Correct 91 ms 18004 KB Guessed the password with 5886 queries.
25 Correct 309 ms 17952 KB Guessed the password with 32337 queries.
26 Correct 198 ms 17956 KB Guessed the password with 16745 queries.
27 Correct 497 ms 17948 KB Guessed the password with 46957 queries.
28 Correct 254 ms 17972 KB Guessed the password with 16697 queries.
29 Runtime error 440 ms 36144 KB Execution killed with signal 6
30 Halted 0 ms 0 KB -