oj.uz

Submission #557471

# Submission time Handle Problem Language Result Execution time Memory
557471 2022-05-05T10:47:59 Z FatihSolak Password (RMI18_password) C++17
80 / 100
 558 ms 36236 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--){
            vector<bool> ok(s);
            for(int i = 0;i<s;i++){
                for(int j = 0;j<s;j++){
                    if(i == j)continue;
                    if(ask2(v[i],v[j],cnt[v[i]],init[v[j]]) >= cnt[v[i]] + used[v[j]] + 1){
                        ok[i] = 1;
                    }
                }
            }
            int val = 0;
            while(cnt[v[val]] == 0 || ok[val])
                val++;
            for(int i = val+1;i<s;i++){
                if(cnt[v[i]] == 0 || ok[i] || cnt[v[val]] == x+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:85:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             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 90 queries.
2 Correct 9 ms 17872 KB Guessed the password with 153 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 17888 KB Guessed the password with 23 queries.
2 Correct 8 ms 17872 KB Guessed the password with 43 queries.
3 Correct 8 ms 17820 KB Guessed the password with 9 queries.
4 Correct 8 ms 17872 KB Guessed the password with 110 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 17940 KB Guessed the password with 1792 queries.
2 Correct 41 ms 17920 KB Guessed the password with 1973 queries.
3 Correct 55 ms 17944 KB Guessed the password with 4460 queries.
4 Correct 84 ms 17924 KB Guessed the password with 8180 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17872 KB Guessed the password with 90 queries.
2 Correct 9 ms 17872 KB Guessed the password with 153 queries.
3 Correct 7 ms 17888 KB Guessed the password with 23 queries.
4 Correct 8 ms 17872 KB Guessed the password with 43 queries.
5 Correct 8 ms 17820 KB Guessed the password with 9 queries.
6 Correct 8 ms 17872 KB Guessed the password with 110 queries.
7 Correct 36 ms 17940 KB Guessed the password with 1792 queries.
8 Correct 41 ms 17920 KB Guessed the password with 1973 queries.
9 Correct 55 ms 17944 KB Guessed the password with 4460 queries.
10 Correct 84 ms 17924 KB Guessed the password with 8180 queries.
11 Correct 93 ms 17952 KB Guessed the password with 7478 queries.
12 Correct 100 ms 17956 KB Guessed the password with 7645 queries.
13 Correct 140 ms 17952 KB Guessed the password with 11340 queries.
14 Correct 163 ms 17948 KB Guessed the password with 10781 queries.
15 Correct 116 ms 17952 KB Guessed the password with 11735 queries.
16 Correct 126 ms 17948 KB Guessed the password with 11864 queries.
17 Correct 108 ms 17960 KB Guessed the password with 8411 queries.
18 Correct 90 ms 18076 KB Guessed the password with 7860 queries.
19 Correct 110 ms 17952 KB Guessed the password with 8738 queries.
20 Correct 131 ms 17960 KB Guessed the password with 9001 queries.
21 Correct 55 ms 17952 KB Guessed the password with 3190 queries.
22 Correct 62 ms 17964 KB Guessed the password with 2840 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17872 KB Guessed the password with 90 queries.
2 Correct 9 ms 17872 KB Guessed the password with 153 queries.
3 Correct 7 ms 17888 KB Guessed the password with 23 queries.
4 Correct 8 ms 17872 KB Guessed the password with 43 queries.
5 Correct 8 ms 17820 KB Guessed the password with 9 queries.
6 Correct 8 ms 17872 KB Guessed the password with 110 queries.
7 Correct 36 ms 17940 KB Guessed the password with 1792 queries.
8 Correct 41 ms 17920 KB Guessed the password with 1973 queries.
9 Correct 55 ms 17944 KB Guessed the password with 4460 queries.
10 Correct 84 ms 17924 KB Guessed the password with 8180 queries.
11 Correct 93 ms 17952 KB Guessed the password with 7478 queries.
12 Correct 100 ms 17956 KB Guessed the password with 7645 queries.
13 Correct 140 ms 17952 KB Guessed the password with 11340 queries.
14 Correct 163 ms 17948 KB Guessed the password with 10781 queries.
15 Correct 116 ms 17952 KB Guessed the password with 11735 queries.
16 Correct 126 ms 17948 KB Guessed the password with 11864 queries.
17 Correct 108 ms 17960 KB Guessed the password with 8411 queries.
18 Correct 90 ms 18076 KB Guessed the password with 7860 queries.
19 Correct 110 ms 17952 KB Guessed the password with 8738 queries.
20 Correct 131 ms 17960 KB Guessed the password with 9001 queries.
21 Correct 55 ms 17952 KB Guessed the password with 3190 queries.
22 Correct 62 ms 17964 KB Guessed the password with 2840 queries.
23 Correct 114 ms 18084 KB Guessed the password with 8445 queries.
24 Correct 103 ms 18072 KB Guessed the password with 5886 queries.
25 Correct 356 ms 17952 KB Guessed the password with 32337 queries.
26 Correct 204 ms 17964 KB Guessed the password with 16745 queries.
27 Correct 466 ms 17952 KB Guessed the password with 46957 queries.
28 Correct 207 ms 17964 KB Guessed the password with 16697 queries.
29 Runtime error 558 ms 36236 KB Execution killed with signal 6
30 Halted 0 ms 0 KB -