oj.uz

Submission #853226

# Submission time Handle Problem Language Result Execution time Memory
853226 2023-09-23T16:46:31 Z allin27x Password (RMI18_password) C++17
100 / 100
 286 ms 2232 KB 
#include <bits/stdc++.h>
using namespace std;
 
int query(string str);
 
string guess(int n, int s){
    mt19937 rng(time(nullptr));
    string res;
    vector<int> nc(s, 0);
    vector<int> to(s, -1);
    for (int i=0; i<s; i++) nc[i] = query(string(n,'a'+i));
    int last = -1;
    while (res.size()<n){
        string rev = res; reverse(rev.begin(), rev.end());
        vector<int> rel;
        for (int i=0; i<s; i++) 
            if (nc[i] && (i==last || to[i] == last)) rel.push_back(i);
        random_shuffle(rel.begin(), rel.end());
        int mx = rel[0];
        for (int i: rel){
            if (i== rel[0]) continue;
            if (!nc[i] || (i!=last && to[i]!=last)) continue;
            if (query(string(nc[i], 'a'+i) + string(1,'a'+mx) + rev) != nc[i] + 1 + res.size()) {
                to[mx] = i;
                mx = i;
            } else {
                to[i] = mx;
            }
        }
        nc[mx] --; res += 'a' + mx;
        last = mx;
    }
    reverse(res.begin(), res.end());
    return res;
}

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:13:22: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   13 |     while (res.size()<n){
      |            ~~~~~~~~~~^~
password.cpp:23:70: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |             if (query(string(nc[i], 'a'+i) + string(1,'a'+mx) + rev) != nc[i] + 1 + res.size()) {
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 68 queries.
2 Correct 1 ms 344 KB Guessed the password with 132 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 48 queries.
2 Correct 1 ms 344 KB Guessed the password with 111 queries.
3 Correct 0 ms 344 KB Guessed the password with 15 queries.
4 Correct 1 ms 344 KB Guessed the password with 195 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 948 KB Guessed the password with 3548 queries.
2 Correct 29 ms 972 KB Guessed the password with 5242 queries.
3 Correct 37 ms 976 KB Guessed the password with 7345 queries.
4 Correct 61 ms 976 KB Guessed the password with 11997 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 68 queries.
2 Correct 1 ms 344 KB Guessed the password with 132 queries.
3 Correct 1 ms 344 KB Guessed the password with 48 queries.
4 Correct 1 ms 344 KB Guessed the password with 111 queries.
5 Correct 0 ms 344 KB Guessed the password with 15 queries.
6 Correct 1 ms 344 KB Guessed the password with 195 queries.
7 Correct 17 ms 948 KB Guessed the password with 3548 queries.
8 Correct 29 ms 972 KB Guessed the password with 5242 queries.
9 Correct 37 ms 976 KB Guessed the password with 7345 queries.
10 Correct 61 ms 976 KB Guessed the password with 11997 queries.
11 Correct 87 ms 952 KB Guessed the password with 12976 queries.
12 Correct 69 ms 1196 KB Guessed the password with 13699 queries.
13 Correct 90 ms 1212 KB Guessed the password with 18783 queries.
14 Correct 100 ms 952 KB Guessed the password with 18140 queries.
15 Correct 96 ms 1448 KB Guessed the password with 18292 queries.
16 Correct 95 ms 1188 KB Guessed the password with 18715 queries.
17 Correct 90 ms 740 KB Guessed the password with 16100 queries.
18 Correct 89 ms 1220 KB Guessed the password with 15357 queries.
19 Correct 78 ms 980 KB Guessed the password with 15341 queries.
20 Correct 87 ms 1228 KB Guessed the password with 15986 queries.
21 Correct 67 ms 1236 KB Guessed the password with 11897 queries.
22 Correct 67 ms 1220 KB Guessed the password with 12250 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 68 queries.
2 Correct 1 ms 344 KB Guessed the password with 132 queries.
3 Correct 1 ms 344 KB Guessed the password with 48 queries.
4 Correct 1 ms 344 KB Guessed the password with 111 queries.
5 Correct 0 ms 344 KB Guessed the password with 15 queries.
6 Correct 1 ms 344 KB Guessed the password with 195 queries.
7 Correct 17 ms 948 KB Guessed the password with 3548 queries.
8 Correct 29 ms 972 KB Guessed the password with 5242 queries.
9 Correct 37 ms 976 KB Guessed the password with 7345 queries.
10 Correct 61 ms 976 KB Guessed the password with 11997 queries.
11 Correct 87 ms 952 KB Guessed the password with 12976 queries.
12 Correct 69 ms 1196 KB Guessed the password with 13699 queries.
13 Correct 90 ms 1212 KB Guessed the password with 18783 queries.
14 Correct 100 ms 952 KB Guessed the password with 18140 queries.
15 Correct 96 ms 1448 KB Guessed the password with 18292 queries.
16 Correct 95 ms 1188 KB Guessed the password with 18715 queries.
17 Correct 90 ms 740 KB Guessed the password with 16100 queries.
18 Correct 89 ms 1220 KB Guessed the password with 15357 queries.
19 Correct 78 ms 980 KB Guessed the password with 15341 queries.
20 Correct 87 ms 1228 KB Guessed the password with 15986 queries.
21 Correct 67 ms 1236 KB Guessed the password with 11897 queries.
22 Correct 67 ms 1220 KB Guessed the password with 12250 queries.
23 Correct 143 ms 1756 KB Guessed the password with 24518 queries.
24 Correct 131 ms 2232 KB Guessed the password with 22126 queries.
25 Correct 212 ms 1628 KB Guessed the password with 36586 queries.
26 Correct 182 ms 2132 KB Guessed the password with 30655 queries.
27 Correct 261 ms 1572 KB Guessed the password with 40810 queries.
28 Correct 186 ms 1800 KB Guessed the password with 28336 queries.
29 Correct 286 ms 1676 KB Guessed the password with 42781 queries.
30 Correct 154 ms 1488 KB Guessed the password with 24128 queries.