oj.uz

Submission #557429

# Submission time Handle Problem Language Result Execution time Memory
557429 2022-05-05T10:25:21 Z FatihSolak Password (RMI18_password) C++17
80 / 100
 1409 ms 18108 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 9 ms 17840 KB Guessed the password with 76 queries.
2 Correct 9 ms 17872 KB Guessed the password with 181 queries.

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 17916 KB Guessed the password with 2155 queries.
2 Correct 75 ms 17924 KB Guessed the password with 3372 queries.
3 Correct 98 ms 17920 KB Guessed the password with 4941 queries.
4 Correct 241 ms 17924 KB Guessed the password with 10806 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17840 KB Guessed the password with 76 queries.
2 Correct 9 ms 17872 KB Guessed the password with 181 queries.
3 Correct 9 ms 17872 KB Guessed the password with 22 queries.
4 Correct 8 ms 17872 KB Guessed the password with 47 queries.
5 Correct 9 ms 17872 KB Guessed the password with 9 queries.
6 Correct 11 ms 17864 KB Guessed the password with 114 queries.
7 Correct 32 ms 17916 KB Guessed the password with 2155 queries.
8 Correct 75 ms 17924 KB Guessed the password with 3372 queries.
9 Correct 98 ms 17920 KB Guessed the password with 4941 queries.
10 Correct 241 ms 17924 KB Guessed the password with 10806 queries.
11 Correct 248 ms 17932 KB Guessed the password with 8539 queries.
12 Correct 234 ms 17932 KB Guessed the password with 8793 queries.
13 Correct 360 ms 17948 KB Guessed the password with 14740 queries.
14 Correct 388 ms 17936 KB Guessed the password with 14737 queries.
15 Correct 341 ms 17932 KB Guessed the password with 13690 queries.
16 Correct 386 ms 17932 KB Guessed the password with 13758 queries.
17 Correct 293 ms 17928 KB Guessed the password with 9998 queries.
18 Correct 259 ms 17940 KB Guessed the password with 9662 queries.
19 Correct 292 ms 17872 KB Guessed the password with 9888 queries.
20 Correct 309 ms 17872 KB Guessed the password with 10170 queries.
21 Correct 156 ms 17904 KB Guessed the password with 5514 queries.
22 Correct 147 ms 17872 KB Guessed the password with 5333 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17840 KB Guessed the password with 76 queries.
2 Correct 9 ms 17872 KB Guessed the password with 181 queries.
3 Correct 9 ms 17872 KB Guessed the password with 22 queries.
4 Correct 8 ms 17872 KB Guessed the password with 47 queries.
5 Correct 9 ms 17872 KB Guessed the password with 9 queries.
6 Correct 11 ms 17864 KB Guessed the password with 114 queries.
7 Correct 32 ms 17916 KB Guessed the password with 2155 queries.
8 Correct 75 ms 17924 KB Guessed the password with 3372 queries.
9 Correct 98 ms 17920 KB Guessed the password with 4941 queries.
10 Correct 241 ms 17924 KB Guessed the password with 10806 queries.
11 Correct 248 ms 17932 KB Guessed the password with 8539 queries.
12 Correct 234 ms 17932 KB Guessed the password with 8793 queries.
13 Correct 360 ms 17948 KB Guessed the password with 14740 queries.
14 Correct 388 ms 17936 KB Guessed the password with 14737 queries.
15 Correct 341 ms 17932 KB Guessed the password with 13690 queries.
16 Correct 386 ms 17932 KB Guessed the password with 13758 queries.
17 Correct 293 ms 17928 KB Guessed the password with 9998 queries.
18 Correct 259 ms 17940 KB Guessed the password with 9662 queries.
19 Correct 292 ms 17872 KB Guessed the password with 9888 queries.
20 Correct 309 ms 17872 KB Guessed the password with 10170 queries.
21 Correct 156 ms 17904 KB Guessed the password with 5514 queries.
22 Correct 147 ms 17872 KB Guessed the password with 5333 queries.
23 Correct 814 ms 18088 KB Guessed the password with 21010 queries.
24 Correct 619 ms 18016 KB Guessed the password with 13499 queries.
25 Execution timed out 1409 ms 18108 KB Time limit exceeded (wall clock)
26 Halted 0 ms 0 KB -