oj.uz

Submission #557436

# Submission time Handle Problem Language Result Execution time Memory
557436 2022-05-05T10:31:40 Z FatihSolak Password (RMI18_password) C++17
80 / 100
 418 ms 36184 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);
}
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--){
        int val = 0;
        while(cnt[v[val]] == 0)
            val++;
        for(int i = val+1;i<s;i++){
            if(cnt[v[i]] == 0)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:73:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(int i = val+1;i<v.size();i++){
      |                           ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17868 KB Guessed the password with 97 queries.
2 Correct 12 ms 17872 KB Guessed the password with 179 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 17872 KB Guessed the password with 22 queries.
2 Correct 8 ms 17872 KB Guessed the password with 46 queries.
3 Correct 9 ms 17856 KB Guessed the password with 8 queries.
4 Correct 8 ms 17872 KB Guessed the password with 113 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 17872 KB Guessed the password with 2147 queries.
2 Correct 30 ms 17916 KB Guessed the password with 3385 queries.
3 Correct 59 ms 18048 KB Guessed the password with 4952 queries.
4 Correct 105 ms 17936 KB Guessed the password with 10814 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17868 KB Guessed the password with 97 queries.
2 Correct 12 ms 17872 KB Guessed the password with 179 queries.
3 Correct 7 ms 17872 KB Guessed the password with 22 queries.
4 Correct 8 ms 17872 KB Guessed the password with 46 queries.
5 Correct 9 ms 17856 KB Guessed the password with 8 queries.
6 Correct 8 ms 17872 KB Guessed the password with 113 queries.
7 Correct 34 ms 17872 KB Guessed the password with 2147 queries.
8 Correct 30 ms 17916 KB Guessed the password with 3385 queries.
9 Correct 59 ms 18048 KB Guessed the password with 4952 queries.
10 Correct 105 ms 17936 KB Guessed the password with 10814 queries.
11 Correct 105 ms 17956 KB Guessed the password with 8540 queries.
12 Correct 100 ms 17948 KB Guessed the password with 8765 queries.
13 Correct 123 ms 17924 KB Guessed the password with 14738 queries.
14 Correct 158 ms 17932 KB Guessed the password with 14706 queries.
15 Correct 125 ms 18000 KB Guessed the password with 13628 queries.
16 Correct 133 ms 17956 KB Guessed the password with 13758 queries.
17 Correct 107 ms 18080 KB Guessed the password with 9991 queries.
18 Correct 116 ms 17956 KB Guessed the password with 9668 queries.
19 Correct 150 ms 18072 KB Guessed the password with 9863 queries.
20 Correct 139 ms 18080 KB Guessed the password with 10152 queries.
21 Correct 53 ms 17952 KB Guessed the password with 5488 queries.
22 Correct 83 ms 17992 KB Guessed the password with 5337 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17868 KB Guessed the password with 97 queries.
2 Correct 12 ms 17872 KB Guessed the password with 179 queries.
3 Correct 7 ms 17872 KB Guessed the password with 22 queries.
4 Correct 8 ms 17872 KB Guessed the password with 46 queries.
5 Correct 9 ms 17856 KB Guessed the password with 8 queries.
6 Correct 8 ms 17872 KB Guessed the password with 113 queries.
7 Correct 34 ms 17872 KB Guessed the password with 2147 queries.
8 Correct 30 ms 17916 KB Guessed the password with 3385 queries.
9 Correct 59 ms 18048 KB Guessed the password with 4952 queries.
10 Correct 105 ms 17936 KB Guessed the password with 10814 queries.
11 Correct 105 ms 17956 KB Guessed the password with 8540 queries.
12 Correct 100 ms 17948 KB Guessed the password with 8765 queries.
13 Correct 123 ms 17924 KB Guessed the password with 14738 queries.
14 Correct 158 ms 17932 KB Guessed the password with 14706 queries.
15 Correct 125 ms 18000 KB Guessed the password with 13628 queries.
16 Correct 133 ms 17956 KB Guessed the password with 13758 queries.
17 Correct 107 ms 18080 KB Guessed the password with 9991 queries.
18 Correct 116 ms 17956 KB Guessed the password with 9668 queries.
19 Correct 150 ms 18072 KB Guessed the password with 9863 queries.
20 Correct 139 ms 18080 KB Guessed the password with 10152 queries.
21 Correct 53 ms 17952 KB Guessed the password with 5488 queries.
22 Correct 83 ms 17992 KB Guessed the password with 5337 queries.
23 Correct 214 ms 17948 KB Guessed the password with 20988 queries.
24 Correct 172 ms 18000 KB Guessed the password with 13471 queries.
25 Correct 340 ms 17948 KB Guessed the password with 43458 queries.
26 Correct 197 ms 17952 KB Guessed the password with 23125 queries.
27 Runtime error 418 ms 36184 KB Execution killed with signal 6
28 Halted 0 ms 0 KB -