oj.uz

Submission #557454

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 17892 KB Guessed the password with 2144 queries.
2 Correct 39 ms 17920 KB Guessed the password with 3375 queries.
3 Correct 64 ms 17932 KB Guessed the password with 4948 queries.
4 Correct 105 ms 17924 KB Guessed the password with 10794 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17872 KB Guessed the password with 86 queries.
2 Correct 9 ms 17872 KB Guessed the password with 154 queries.
3 Correct 8 ms 17872 KB Guessed the password with 23 queries.
4 Correct 7 ms 17872 KB Guessed the password with 48 queries.
5 Correct 8 ms 17908 KB Guessed the password with 8 queries.
6 Correct 8 ms 17872 KB Guessed the password with 114 queries.
7 Correct 31 ms 17892 KB Guessed the password with 2144 queries.
8 Correct 39 ms 17920 KB Guessed the password with 3375 queries.
9 Correct 64 ms 17932 KB Guessed the password with 4948 queries.
10 Correct 105 ms 17924 KB Guessed the password with 10794 queries.
11 Correct 101 ms 17956 KB Guessed the password with 8542 queries.
12 Correct 113 ms 17948 KB Guessed the password with 8716 queries.
13 Correct 111 ms 18000 KB Guessed the password with 14799 queries.
14 Correct 98 ms 17948 KB Guessed the password with 14667 queries.
15 Correct 163 ms 18004 KB Guessed the password with 13661 queries.
16 Correct 151 ms 18072 KB Guessed the password with 13711 queries.
17 Correct 122 ms 17968 KB Guessed the password with 10057 queries.
18 Correct 98 ms 17992 KB Guessed the password with 9592 queries.
19 Correct 139 ms 18080 KB Guessed the password with 9953 queries.
20 Correct 128 ms 17960 KB Guessed the password with 10149 queries.
21 Correct 79 ms 17872 KB Guessed the password with 5567 queries.
22 Correct 71 ms 17952 KB Guessed the password with 5253 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17872 KB Guessed the password with 86 queries.
2 Correct 9 ms 17872 KB Guessed the password with 154 queries.
3 Correct 8 ms 17872 KB Guessed the password with 23 queries.
4 Correct 7 ms 17872 KB Guessed the password with 48 queries.
5 Correct 8 ms 17908 KB Guessed the password with 8 queries.
6 Correct 8 ms 17872 KB Guessed the password with 114 queries.
7 Correct 31 ms 17892 KB Guessed the password with 2144 queries.
8 Correct 39 ms 17920 KB Guessed the password with 3375 queries.
9 Correct 64 ms 17932 KB Guessed the password with 4948 queries.
10 Correct 105 ms 17924 KB Guessed the password with 10794 queries.
11 Correct 101 ms 17956 KB Guessed the password with 8542 queries.
12 Correct 113 ms 17948 KB Guessed the password with 8716 queries.
13 Correct 111 ms 18000 KB Guessed the password with 14799 queries.
14 Correct 98 ms 17948 KB Guessed the password with 14667 queries.
15 Correct 163 ms 18004 KB Guessed the password with 13661 queries.
16 Correct 151 ms 18072 KB Guessed the password with 13711 queries.
17 Correct 122 ms 17968 KB Guessed the password with 10057 queries.
18 Correct 98 ms 17992 KB Guessed the password with 9592 queries.
19 Correct 139 ms 18080 KB Guessed the password with 9953 queries.
20 Correct 128 ms 17960 KB Guessed the password with 10149 queries.
21 Correct 79 ms 17872 KB Guessed the password with 5567 queries.
22 Correct 71 ms 17952 KB Guessed the password with 5253 queries.
23 Correct 221 ms 17948 KB Guessed the password with 20992 queries.
24 Correct 151 ms 18024 KB Guessed the password with 13505 queries.
25 Correct 458 ms 18068 KB Guessed the password with 43440 queries.
26 Correct 257 ms 18084 KB Guessed the password with 23157 queries.
27 Runtime error 505 ms 36240 KB Execution killed with signal 6
28 Halted 0 ms 0 KB -