oj.uz

Submission #557430

# Submission time Handle Problem Language Result Execution time Memory
557430 2022-05-05T10:25:52 Z FatihSolak Password (RMI18_password) C++17
80 / 100
 1409 ms 18232 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++){
        cnt[v[i]] = ask(v[i],0,n,0);
    }
    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:71:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         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 17868 KB Guessed the password with 76 queries.
2 Correct 10 ms 17864 KB Guessed the password with 181 queries.

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 17872 KB Guessed the password with 2155 queries.
2 Correct 72 ms 17940 KB Guessed the password with 3372 queries.
3 Correct 102 ms 17936 KB Guessed the password with 4941 queries.
4 Correct 257 ms 17928 KB Guessed the password with 10806 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17868 KB Guessed the password with 76 queries.
2 Correct 10 ms 17864 KB Guessed the password with 181 queries.
3 Correct 8 ms 17888 KB Guessed the password with 22 queries.
4 Correct 8 ms 17872 KB Guessed the password with 47 queries.
5 Correct 7 ms 17808 KB Guessed the password with 9 queries.
6 Correct 9 ms 17872 KB Guessed the password with 114 queries.
7 Correct 43 ms 17872 KB Guessed the password with 2155 queries.
8 Correct 72 ms 17940 KB Guessed the password with 3372 queries.
9 Correct 102 ms 17936 KB Guessed the password with 4941 queries.
10 Correct 257 ms 17928 KB Guessed the password with 10806 queries.
11 Correct 244 ms 17928 KB Guessed the password with 8539 queries.
12 Correct 250 ms 17928 KB Guessed the password with 8793 queries.
13 Correct 366 ms 17928 KB Guessed the password with 14740 queries.
14 Correct 398 ms 17928 KB Guessed the password with 14737 queries.
15 Correct 365 ms 17944 KB Guessed the password with 13690 queries.
16 Correct 367 ms 17928 KB Guessed the password with 13758 queries.
17 Correct 295 ms 17928 KB Guessed the password with 9998 queries.
18 Correct 278 ms 17928 KB Guessed the password with 9662 queries.
19 Correct 286 ms 17932 KB Guessed the password with 9888 queries.
20 Correct 298 ms 17940 KB Guessed the password with 10170 queries.
21 Correct 168 ms 17992 KB Guessed the password with 5514 queries.
22 Correct 163 ms 17944 KB Guessed the password with 5333 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17868 KB Guessed the password with 76 queries.
2 Correct 10 ms 17864 KB Guessed the password with 181 queries.
3 Correct 8 ms 17888 KB Guessed the password with 22 queries.
4 Correct 8 ms 17872 KB Guessed the password with 47 queries.
5 Correct 7 ms 17808 KB Guessed the password with 9 queries.
6 Correct 9 ms 17872 KB Guessed the password with 114 queries.
7 Correct 43 ms 17872 KB Guessed the password with 2155 queries.
8 Correct 72 ms 17940 KB Guessed the password with 3372 queries.
9 Correct 102 ms 17936 KB Guessed the password with 4941 queries.
10 Correct 257 ms 17928 KB Guessed the password with 10806 queries.
11 Correct 244 ms 17928 KB Guessed the password with 8539 queries.
12 Correct 250 ms 17928 KB Guessed the password with 8793 queries.
13 Correct 366 ms 17928 KB Guessed the password with 14740 queries.
14 Correct 398 ms 17928 KB Guessed the password with 14737 queries.
15 Correct 365 ms 17944 KB Guessed the password with 13690 queries.
16 Correct 367 ms 17928 KB Guessed the password with 13758 queries.
17 Correct 295 ms 17928 KB Guessed the password with 9998 queries.
18 Correct 278 ms 17928 KB Guessed the password with 9662 queries.
19 Correct 286 ms 17932 KB Guessed the password with 9888 queries.
20 Correct 298 ms 17940 KB Guessed the password with 10170 queries.
21 Correct 168 ms 17992 KB Guessed the password with 5514 queries.
22 Correct 163 ms 17944 KB Guessed the password with 5333 queries.
23 Correct 841 ms 18132 KB Guessed the password with 21010 queries.
24 Correct 544 ms 18124 KB Guessed the password with 13499 queries.
25 Execution timed out 1409 ms 18232 KB Time limit exceeded (wall clock)
26 Halted 0 ms 0 KB -