oj.uz

Submission #557432

# Submission time Handle Problem Language Result Execution time Memory
557432 2022-05-05T10:29:09 Z FatihSolak Password (RMI18_password) C++17
80 / 100
 1394 ms 18152 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(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);
    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 9 ms 17872 KB Guessed the password with 97 queries.
2 Correct 9 ms 17872 KB Guessed the password with 179 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 17872 KB Guessed the password with 22 queries.
2 Correct 8 ms 17848 KB Guessed the password with 46 queries.
3 Correct 8 ms 17808 KB Guessed the password with 8 queries.
4 Correct 9 ms 17812 KB Guessed the password with 113 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 17936 KB Guessed the password with 2147 queries.
2 Correct 70 ms 17940 KB Guessed the password with 3385 queries.
3 Correct 92 ms 17936 KB Guessed the password with 4952 queries.
4 Correct 263 ms 17940 KB Guessed the password with 10814 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17872 KB Guessed the password with 97 queries.
2 Correct 9 ms 17872 KB Guessed the password with 179 queries.
3 Correct 7 ms 17872 KB Guessed the password with 22 queries.
4 Correct 8 ms 17848 KB Guessed the password with 46 queries.
5 Correct 8 ms 17808 KB Guessed the password with 8 queries.
6 Correct 9 ms 17812 KB Guessed the password with 113 queries.
7 Correct 32 ms 17936 KB Guessed the password with 2147 queries.
8 Correct 70 ms 17940 KB Guessed the password with 3385 queries.
9 Correct 92 ms 17936 KB Guessed the password with 4952 queries.
10 Correct 263 ms 17940 KB Guessed the password with 10814 queries.
11 Correct 196 ms 17924 KB Guessed the password with 8540 queries.
12 Correct 209 ms 17928 KB Guessed the password with 8765 queries.
13 Correct 369 ms 17924 KB Guessed the password with 14738 queries.
14 Correct 395 ms 17924 KB Guessed the password with 14706 queries.
15 Correct 352 ms 17932 KB Guessed the password with 13628 queries.
16 Correct 361 ms 17932 KB Guessed the password with 13758 queries.
17 Correct 280 ms 17932 KB Guessed the password with 9991 queries.
18 Correct 296 ms 17928 KB Guessed the password with 9668 queries.
19 Correct 283 ms 17992 KB Guessed the password with 9863 queries.
20 Correct 283 ms 17936 KB Guessed the password with 10152 queries.
21 Correct 169 ms 17936 KB Guessed the password with 5488 queries.
22 Correct 170 ms 17928 KB Guessed the password with 5337 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17872 KB Guessed the password with 97 queries.
2 Correct 9 ms 17872 KB Guessed the password with 179 queries.
3 Correct 7 ms 17872 KB Guessed the password with 22 queries.
4 Correct 8 ms 17848 KB Guessed the password with 46 queries.
5 Correct 8 ms 17808 KB Guessed the password with 8 queries.
6 Correct 9 ms 17812 KB Guessed the password with 113 queries.
7 Correct 32 ms 17936 KB Guessed the password with 2147 queries.
8 Correct 70 ms 17940 KB Guessed the password with 3385 queries.
9 Correct 92 ms 17936 KB Guessed the password with 4952 queries.
10 Correct 263 ms 17940 KB Guessed the password with 10814 queries.
11 Correct 196 ms 17924 KB Guessed the password with 8540 queries.
12 Correct 209 ms 17928 KB Guessed the password with 8765 queries.
13 Correct 369 ms 17924 KB Guessed the password with 14738 queries.
14 Correct 395 ms 17924 KB Guessed the password with 14706 queries.
15 Correct 352 ms 17932 KB Guessed the password with 13628 queries.
16 Correct 361 ms 17932 KB Guessed the password with 13758 queries.
17 Correct 280 ms 17932 KB Guessed the password with 9991 queries.
18 Correct 296 ms 17928 KB Guessed the password with 9668 queries.
19 Correct 283 ms 17992 KB Guessed the password with 9863 queries.
20 Correct 283 ms 17936 KB Guessed the password with 10152 queries.
21 Correct 169 ms 17936 KB Guessed the password with 5488 queries.
22 Correct 170 ms 17928 KB Guessed the password with 5337 queries.
23 Correct 898 ms 18152 KB Guessed the password with 20988 queries.
24 Correct 615 ms 18060 KB Guessed the password with 13471 queries.
25 Execution timed out 1394 ms 18120 KB Time limit exceeded (wall clock)
26 Halted 0 ms 0 KB -