oj.uz

Submission #557457

# Submission time Handle Problem Language Result Execution time Memory
557457 2022-05-05T10:40:57 Z FatihSolak Password (RMI18_password) C++17
80 / 100
 540 ms 36244 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--){
        int val = 0;
        while(cnt[v[val]] == 0)
            val++;
        for(int i = val+1;i<s;i++){
            if(cnt[v[i]] == 0)continue;
            if(ask2(v[i],v[val],cnt[v[i]],init[v[val]]) >= cnt[v[i]] + used[v[val]] + 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:79:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         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 12 ms 17872 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 9 ms 17872 KB Guessed the password with 48 queries.
3 Correct 10 ms 17852 KB Guessed the password with 8 queries.
4 Correct 11 ms 17832 KB Guessed the password with 114 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 17944 KB Guessed the password with 2144 queries.
2 Correct 37 ms 17924 KB Guessed the password with 3375 queries.
3 Correct 58 ms 17936 KB Guessed the password with 4948 queries.
4 Correct 125 ms 17960 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 12 ms 17872 KB Guessed the password with 154 queries.
3 Correct 9 ms 17872 KB Guessed the password with 23 queries.
4 Correct 9 ms 17872 KB Guessed the password with 48 queries.
5 Correct 10 ms 17852 KB Guessed the password with 8 queries.
6 Correct 11 ms 17832 KB Guessed the password with 114 queries.
7 Correct 27 ms 17944 KB Guessed the password with 2144 queries.
8 Correct 37 ms 17924 KB Guessed the password with 3375 queries.
9 Correct 58 ms 17936 KB Guessed the password with 4948 queries.
10 Correct 125 ms 17960 KB Guessed the password with 10794 queries.
11 Correct 115 ms 17952 KB Guessed the password with 8542 queries.
12 Correct 93 ms 17952 KB Guessed the password with 8716 queries.
13 Correct 152 ms 17944 KB Guessed the password with 14799 queries.
14 Correct 180 ms 17944 KB Guessed the password with 14667 queries.
15 Correct 161 ms 18020 KB Guessed the password with 13661 queries.
16 Correct 169 ms 17952 KB Guessed the password with 13711 queries.
17 Correct 94 ms 17948 KB Guessed the password with 10057 queries.
18 Correct 136 ms 17960 KB Guessed the password with 9592 queries.
19 Correct 121 ms 17956 KB Guessed the password with 9953 queries.
20 Correct 153 ms 17952 KB Guessed the password with 10149 queries.
21 Correct 85 ms 17956 KB Guessed the password with 5567 queries.
22 Correct 92 ms 17936 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 12 ms 17872 KB Guessed the password with 154 queries.
3 Correct 9 ms 17872 KB Guessed the password with 23 queries.
4 Correct 9 ms 17872 KB Guessed the password with 48 queries.
5 Correct 10 ms 17852 KB Guessed the password with 8 queries.
6 Correct 11 ms 17832 KB Guessed the password with 114 queries.
7 Correct 27 ms 17944 KB Guessed the password with 2144 queries.
8 Correct 37 ms 17924 KB Guessed the password with 3375 queries.
9 Correct 58 ms 17936 KB Guessed the password with 4948 queries.
10 Correct 125 ms 17960 KB Guessed the password with 10794 queries.
11 Correct 115 ms 17952 KB Guessed the password with 8542 queries.
12 Correct 93 ms 17952 KB Guessed the password with 8716 queries.
13 Correct 152 ms 17944 KB Guessed the password with 14799 queries.
14 Correct 180 ms 17944 KB Guessed the password with 14667 queries.
15 Correct 161 ms 18020 KB Guessed the password with 13661 queries.
16 Correct 169 ms 17952 KB Guessed the password with 13711 queries.
17 Correct 94 ms 17948 KB Guessed the password with 10057 queries.
18 Correct 136 ms 17960 KB Guessed the password with 9592 queries.
19 Correct 121 ms 17956 KB Guessed the password with 9953 queries.
20 Correct 153 ms 17952 KB Guessed the password with 10149 queries.
21 Correct 85 ms 17956 KB Guessed the password with 5567 queries.
22 Correct 92 ms 17936 KB Guessed the password with 5253 queries.
23 Correct 249 ms 17960 KB Guessed the password with 20992 queries.
24 Correct 173 ms 17952 KB Guessed the password with 13505 queries.
25 Correct 462 ms 17956 KB Guessed the password with 43440 queries.
26 Correct 223 ms 18056 KB Guessed the password with 23157 queries.
27 Runtime error 540 ms 36244 KB Execution killed with signal 6
28 Halted 0 ms 0 KB -