oj.uz

Submission #557420

# Submission time Handle Problem Language Result Execution time Memory
557420 2022-05-05T10:19:00 Z FatihSolak Password (RMI18_password) C++17
80 / 100
 1420 ms 18164 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 += (char)(a + 'a');
    for(int i = 0;i<d;i++)
        tmp += (char)(b + 'a');
    return rem[a][b][c] = myquery(tmp);
}
mt19937 rng(58);
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);
    for(int i = 0;i<s;i++){
        string tmp = "";
        for(int j = 0;j<n;j++)
            tmp += (char) (v[i] + 'a');
        //cout << tmp << endl;
        cnt[v[i]] = myquery(tmp);
        //cout << cnt[i] << endl;
    }
    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]],n-cnt[v[val]]) >= cnt[v[val]] + used[v[i]] + 1){
                val = i;
            }
        }
        res += (char)(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:76:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for(int i = val+1;i<v.size();i++){
      |                           ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17872 KB Guessed the password with 76 queries.
2 Correct 10 ms 17872 KB Guessed the password with 181 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17920 KB Guessed the password with 22 queries.
2 Correct 8 ms 17808 KB Guessed the password with 47 queries.
3 Correct 8 ms 17840 KB Guessed the password with 9 queries.
4 Correct 11 ms 17872 KB Guessed the password with 114 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 17928 KB Guessed the password with 2155 queries.
2 Correct 73 ms 17924 KB Guessed the password with 3372 queries.
3 Correct 97 ms 17880 KB Guessed the password with 4941 queries.
4 Correct 204 ms 17944 KB Guessed the password with 10806 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17872 KB Guessed the password with 76 queries.
2 Correct 10 ms 17872 KB Guessed the password with 181 queries.
3 Correct 8 ms 17920 KB Guessed the password with 22 queries.
4 Correct 8 ms 17808 KB Guessed the password with 47 queries.
5 Correct 8 ms 17840 KB Guessed the password with 9 queries.
6 Correct 11 ms 17872 KB Guessed the password with 114 queries.
7 Correct 41 ms 17928 KB Guessed the password with 2155 queries.
8 Correct 73 ms 17924 KB Guessed the password with 3372 queries.
9 Correct 97 ms 17880 KB Guessed the password with 4941 queries.
10 Correct 204 ms 17944 KB Guessed the password with 10806 queries.
11 Correct 202 ms 17932 KB Guessed the password with 8539 queries.
12 Correct 222 ms 17872 KB Guessed the password with 8793 queries.
13 Correct 355 ms 17932 KB Guessed the password with 14740 queries.
14 Correct 351 ms 17936 KB Guessed the password with 14737 queries.
15 Correct 371 ms 17928 KB Guessed the password with 13690 queries.
16 Correct 369 ms 17932 KB Guessed the password with 13758 queries.
17 Correct 279 ms 17880 KB Guessed the password with 9998 queries.
18 Correct 286 ms 17944 KB Guessed the password with 9662 queries.
19 Correct 282 ms 17948 KB Guessed the password with 9888 queries.
20 Correct 296 ms 17932 KB Guessed the password with 10170 queries.
21 Correct 171 ms 17932 KB Guessed the password with 5514 queries.
22 Correct 167 ms 17872 KB Guessed the password with 5333 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17872 KB Guessed the password with 76 queries.
2 Correct 10 ms 17872 KB Guessed the password with 181 queries.
3 Correct 8 ms 17920 KB Guessed the password with 22 queries.
4 Correct 8 ms 17808 KB Guessed the password with 47 queries.
5 Correct 8 ms 17840 KB Guessed the password with 9 queries.
6 Correct 11 ms 17872 KB Guessed the password with 114 queries.
7 Correct 41 ms 17928 KB Guessed the password with 2155 queries.
8 Correct 73 ms 17924 KB Guessed the password with 3372 queries.
9 Correct 97 ms 17880 KB Guessed the password with 4941 queries.
10 Correct 204 ms 17944 KB Guessed the password with 10806 queries.
11 Correct 202 ms 17932 KB Guessed the password with 8539 queries.
12 Correct 222 ms 17872 KB Guessed the password with 8793 queries.
13 Correct 355 ms 17932 KB Guessed the password with 14740 queries.
14 Correct 351 ms 17936 KB Guessed the password with 14737 queries.
15 Correct 371 ms 17928 KB Guessed the password with 13690 queries.
16 Correct 369 ms 17932 KB Guessed the password with 13758 queries.
17 Correct 279 ms 17880 KB Guessed the password with 9998 queries.
18 Correct 286 ms 17944 KB Guessed the password with 9662 queries.
19 Correct 282 ms 17948 KB Guessed the password with 9888 queries.
20 Correct 296 ms 17932 KB Guessed the password with 10170 queries.
21 Correct 171 ms 17932 KB Guessed the password with 5514 queries.
22 Correct 167 ms 17872 KB Guessed the password with 5333 queries.
23 Correct 757 ms 18140 KB Guessed the password with 21010 queries.
24 Correct 492 ms 18152 KB Guessed the password with 13499 queries.
25 Execution timed out 1420 ms 18164 KB Time limit exceeded (wall clock)
26 Halted 0 ms 0 KB -