oj.uz

Submission #557446

# Submission time Handle Problem Language Result Execution time Memory
557446 2022-05-05T10:35:30 Z FatihSolak Password (RMI18_password) C++17
80 / 100
 498 ms 36176 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 17872 KB Guessed the password with 86 queries.
2 Correct 10 ms 17872 KB Guessed the password with 154 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17900 KB Guessed the password with 23 queries.
2 Correct 11 ms 17872 KB Guessed the password with 48 queries.
3 Correct 8 ms 17872 KB Guessed the password with 8 queries.
4 Correct 10 ms 17852 KB Guessed the password with 114 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 17940 KB Guessed the password with 2144 queries.
2 Correct 41 ms 17920 KB Guessed the password with 3375 queries.
3 Correct 70 ms 17936 KB Guessed the password with 4948 queries.
4 Correct 122 ms 17932 KB Guessed the password with 10794 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17872 KB Guessed the password with 86 queries.
2 Correct 10 ms 17872 KB Guessed the password with 154 queries.
3 Correct 10 ms 17900 KB Guessed the password with 23 queries.
4 Correct 11 ms 17872 KB Guessed the password with 48 queries.
5 Correct 8 ms 17872 KB Guessed the password with 8 queries.
6 Correct 10 ms 17852 KB Guessed the password with 114 queries.
7 Correct 29 ms 17940 KB Guessed the password with 2144 queries.
8 Correct 41 ms 17920 KB Guessed the password with 3375 queries.
9 Correct 70 ms 17936 KB Guessed the password with 4948 queries.
10 Correct 122 ms 17932 KB Guessed the password with 10794 queries.
11 Correct 87 ms 17956 KB Guessed the password with 8542 queries.
12 Correct 111 ms 17952 KB Guessed the password with 8716 queries.
13 Correct 173 ms 18064 KB Guessed the password with 14799 queries.
14 Correct 171 ms 17952 KB Guessed the password with 14667 queries.
15 Correct 130 ms 17952 KB Guessed the password with 13661 queries.
16 Correct 169 ms 17952 KB Guessed the password with 13711 queries.
17 Correct 134 ms 17956 KB Guessed the password with 10057 queries.
18 Correct 132 ms 17960 KB Guessed the password with 9592 queries.
19 Correct 137 ms 18076 KB Guessed the password with 9953 queries.
20 Correct 143 ms 17948 KB Guessed the password with 10149 queries.
21 Correct 92 ms 17960 KB Guessed the password with 5567 queries.
22 Correct 71 ms 17956 KB Guessed the password with 5253 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17872 KB Guessed the password with 86 queries.
2 Correct 10 ms 17872 KB Guessed the password with 154 queries.
3 Correct 10 ms 17900 KB Guessed the password with 23 queries.
4 Correct 11 ms 17872 KB Guessed the password with 48 queries.
5 Correct 8 ms 17872 KB Guessed the password with 8 queries.
6 Correct 10 ms 17852 KB Guessed the password with 114 queries.
7 Correct 29 ms 17940 KB Guessed the password with 2144 queries.
8 Correct 41 ms 17920 KB Guessed the password with 3375 queries.
9 Correct 70 ms 17936 KB Guessed the password with 4948 queries.
10 Correct 122 ms 17932 KB Guessed the password with 10794 queries.
11 Correct 87 ms 17956 KB Guessed the password with 8542 queries.
12 Correct 111 ms 17952 KB Guessed the password with 8716 queries.
13 Correct 173 ms 18064 KB Guessed the password with 14799 queries.
14 Correct 171 ms 17952 KB Guessed the password with 14667 queries.
15 Correct 130 ms 17952 KB Guessed the password with 13661 queries.
16 Correct 169 ms 17952 KB Guessed the password with 13711 queries.
17 Correct 134 ms 17956 KB Guessed the password with 10057 queries.
18 Correct 132 ms 17960 KB Guessed the password with 9592 queries.
19 Correct 137 ms 18076 KB Guessed the password with 9953 queries.
20 Correct 143 ms 17948 KB Guessed the password with 10149 queries.
21 Correct 92 ms 17960 KB Guessed the password with 5567 queries.
22 Correct 71 ms 17956 KB Guessed the password with 5253 queries.
23 Correct 243 ms 17952 KB Guessed the password with 20992 queries.
24 Correct 121 ms 18080 KB Guessed the password with 13505 queries.
25 Correct 444 ms 17956 KB Guessed the password with 43440 queries.
26 Correct 198 ms 17968 KB Guessed the password with 23157 queries.
27 Runtime error 498 ms 36176 KB Execution killed with signal 6
28 Halted 0 ms 0 KB -