oj.uz

Submission #557431

# Submission time Handle Problem Language Result Execution time Memory
557431 2022-05-05T10:28:05 Z FatihSolak Password (RMI18_password) C++17
80 / 100
 1399 ms 18224 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(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 += 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 8 ms 17872 KB Guessed the password with 76 queries.
2 Correct 12 ms 17900 KB Guessed the password with 181 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17872 KB Guessed the password with 22 queries.
2 Correct 8 ms 17808 KB Guessed the password with 47 queries.
3 Correct 9 ms 17872 KB Guessed the password with 9 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 40 ms 17884 KB Guessed the password with 2155 queries.
2 Correct 67 ms 17924 KB Guessed the password with 3372 queries.
3 Correct 86 ms 17944 KB Guessed the password with 4941 queries.
4 Correct 196 ms 17928 KB Guessed the password with 10806 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17872 KB Guessed the password with 76 queries.
2 Correct 12 ms 17900 KB Guessed the password with 181 queries.
3 Correct 8 ms 17872 KB Guessed the password with 22 queries.
4 Correct 8 ms 17808 KB Guessed the password with 47 queries.
5 Correct 9 ms 17872 KB Guessed the password with 9 queries.
6 Correct 8 ms 17872 KB Guessed the password with 114 queries.
7 Correct 40 ms 17884 KB Guessed the password with 2155 queries.
8 Correct 67 ms 17924 KB Guessed the password with 3372 queries.
9 Correct 86 ms 17944 KB Guessed the password with 4941 queries.
10 Correct 196 ms 17928 KB Guessed the password with 10806 queries.
11 Correct 213 ms 17872 KB Guessed the password with 8539 queries.
12 Correct 216 ms 17992 KB Guessed the password with 8793 queries.
13 Correct 374 ms 17992 KB Guessed the password with 14740 queries.
14 Correct 377 ms 17872 KB Guessed the password with 14737 queries.
15 Correct 365 ms 17928 KB Guessed the password with 13690 queries.
16 Correct 368 ms 17992 KB Guessed the password with 13758 queries.
17 Correct 280 ms 17928 KB Guessed the password with 9998 queries.
18 Correct 274 ms 17928 KB Guessed the password with 9662 queries.
19 Correct 256 ms 17936 KB Guessed the password with 9888 queries.
20 Correct 299 ms 17936 KB Guessed the password with 10170 queries.
21 Correct 169 ms 17928 KB Guessed the password with 5514 queries.
22 Correct 163 ms 17928 KB Guessed the password with 5333 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17872 KB Guessed the password with 76 queries.
2 Correct 12 ms 17900 KB Guessed the password with 181 queries.
3 Correct 8 ms 17872 KB Guessed the password with 22 queries.
4 Correct 8 ms 17808 KB Guessed the password with 47 queries.
5 Correct 9 ms 17872 KB Guessed the password with 9 queries.
6 Correct 8 ms 17872 KB Guessed the password with 114 queries.
7 Correct 40 ms 17884 KB Guessed the password with 2155 queries.
8 Correct 67 ms 17924 KB Guessed the password with 3372 queries.
9 Correct 86 ms 17944 KB Guessed the password with 4941 queries.
10 Correct 196 ms 17928 KB Guessed the password with 10806 queries.
11 Correct 213 ms 17872 KB Guessed the password with 8539 queries.
12 Correct 216 ms 17992 KB Guessed the password with 8793 queries.
13 Correct 374 ms 17992 KB Guessed the password with 14740 queries.
14 Correct 377 ms 17872 KB Guessed the password with 14737 queries.
15 Correct 365 ms 17928 KB Guessed the password with 13690 queries.
16 Correct 368 ms 17992 KB Guessed the password with 13758 queries.
17 Correct 280 ms 17928 KB Guessed the password with 9998 queries.
18 Correct 274 ms 17928 KB Guessed the password with 9662 queries.
19 Correct 256 ms 17936 KB Guessed the password with 9888 queries.
20 Correct 299 ms 17936 KB Guessed the password with 10170 queries.
21 Correct 169 ms 17928 KB Guessed the password with 5514 queries.
22 Correct 163 ms 17928 KB Guessed the password with 5333 queries.
23 Correct 808 ms 18176 KB Guessed the password with 21010 queries.
24 Correct 536 ms 18184 KB Guessed the password with 13499 queries.
25 Execution timed out 1399 ms 18224 KB Time limit exceeded (wall clock)
26 Halted 0 ms 0 KB -