oj.uz

Submission #557456

# Submission time Handle Problem Language Result Execution time Memory
557456 2022-05-05T10:40:24 Z FatihSolak Password (RMI18_password) C++17
50 / 100
 383 ms 36168 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);
}
int ask2(int a,int b,int c,int d){
    return rem[a][b][c];
}
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);
    vector<int> init(s);
    for(int i = 0;i<s;i++){
        cnt[v[i]] = ask(v[i],0,n,0);
        init[v[i]] = cnt[v[i]];
    }
    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(ask2(v[i],v[val],cnt[v[i]],init[v[val]]) >= cnt[v[i]] + used[v[val]] + 1){
                continue;
            }
            if(ask(v[val],v[i],cnt[v[val]],init[v[i]]) >= 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:79:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         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 17876 KB Guessed the password with 86 queries.
2 Correct 9 ms 17872 KB Guessed the password with 154 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 17928 KB Guessed the password with 27 queries.
2 Correct 8 ms 17872 KB Guessed the password with 103 queries.
3 Correct 7 ms 17844 KB Guessed the password with 17 queries.
4 Correct 8 ms 17872 KB Guessed the password with 133 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 17924 KB Guessed the password with 3770 queries.
2 Correct 107 ms 17920 KB Guessed the password with 9261 queries.
3 Correct 106 ms 17872 KB Guessed the password with 9839 queries.
4 Correct 179 ms 17932 KB Guessed the password with 18313 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17876 KB Guessed the password with 86 queries.
2 Correct 9 ms 17872 KB Guessed the password with 154 queries.
3 Correct 7 ms 17928 KB Guessed the password with 27 queries.
4 Correct 8 ms 17872 KB Guessed the password with 103 queries.
5 Correct 7 ms 17844 KB Guessed the password with 17 queries.
6 Correct 8 ms 17872 KB Guessed the password with 133 queries.
7 Correct 49 ms 17924 KB Guessed the password with 3770 queries.
8 Correct 107 ms 17920 KB Guessed the password with 9261 queries.
9 Correct 106 ms 17872 KB Guessed the password with 9839 queries.
10 Correct 179 ms 17932 KB Guessed the password with 18313 queries.
11 Correct 330 ms 17956 KB Guessed the password with 33171 queries.
12 Correct 110 ms 17992 KB Guessed the password with 9059 queries.
13 Correct 360 ms 18060 KB Guessed the password with 46117 queries.
14 Correct 131 ms 17872 KB Guessed the password with 17880 queries.
15 Correct 345 ms 17956 KB Guessed the password with 43506 queries.
16 Correct 138 ms 17948 KB Guessed the password with 16258 queries.
17 Runtime error 383 ms 36168 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17876 KB Guessed the password with 86 queries.
2 Correct 9 ms 17872 KB Guessed the password with 154 queries.
3 Correct 7 ms 17928 KB Guessed the password with 27 queries.
4 Correct 8 ms 17872 KB Guessed the password with 103 queries.
5 Correct 7 ms 17844 KB Guessed the password with 17 queries.
6 Correct 8 ms 17872 KB Guessed the password with 133 queries.
7 Correct 49 ms 17924 KB Guessed the password with 3770 queries.
8 Correct 107 ms 17920 KB Guessed the password with 9261 queries.
9 Correct 106 ms 17872 KB Guessed the password with 9839 queries.
10 Correct 179 ms 17932 KB Guessed the password with 18313 queries.
11 Correct 330 ms 17956 KB Guessed the password with 33171 queries.
12 Correct 110 ms 17992 KB Guessed the password with 9059 queries.
13 Correct 360 ms 18060 KB Guessed the password with 46117 queries.
14 Correct 131 ms 17872 KB Guessed the password with 17880 queries.
15 Correct 345 ms 17956 KB Guessed the password with 43506 queries.
16 Correct 138 ms 17948 KB Guessed the password with 16258 queries.
17 Runtime error 383 ms 36168 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -