oj.uz

Submission #464164

# Submission time Handle Problem Language Result Execution time Memory
464164 2021-08-12T13:21:30 Z Mamedov Password (RMI18_password) C++17
100 / 100
 299 ms 548 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define ui unsigned int
#define pii pair<int, int>
#define pis pair<int, string>
#define piii pair<int, pii>
#define pb push_back
#define f first
#define s second
#define oo (1ll << 60)

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int query(string str);

void combine(string &str, string &add) {   /// str is the smallest one, add is the second smallest
    int str_len = str.length();
    int add_len = add.length();
    vector<int>comesAfter(str_len + 2);
    comesAfter[0] = 0;
    comesAfter[str_len + 1] = add_len;
    int i = str_len;
    int j = add_len - 1;
    while(i >= 1) {
        while(j >= 0) {
            string ask = str.substr(0, i) + add.substr(j);
            if(query(ask) < ask.length()) {
                break;
            }
            --j;
        }
        comesAfter[i] = j + 1;
        --i;
    }
    for(int i = 0; i <= str_len; ++i) {
        for(int j = comesAfter[i]; j < comesAfter[i + 1]; ++j) {
            str.insert(str.begin() + i + j, add[j]);
        }
    }
}
string guess(int n, int s) {
    string str, add;
    priority_queue<pis, vector<pis>, greater<pis>>pq;
    for(int i = 0; i < s; ++i) {
        str = "";
        for(int j = 0; j < n; ++j) {
            str += ('a' + i);
        }
        int Count = query(str);
        if(Count) {
            pq.push({Count, str.substr(0, Count)});
        }
    }
    while(pq.size() > 1) {
        str = (pq.top()).s; pq.pop();
        add = (pq.top()).s; pq.pop();
        combine(str, add);
        pq.push({str.length(), str});
    }
    return (pq.top()).s;
}

Compilation message

password.cpp: In function 'void combine(std::string&, std::string&)':
password.cpp:29:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |             if(query(ask) < ask.length()) {
      |                ~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 59 queries.
2 Correct 2 ms 200 KB Guessed the password with 100 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 48 queries.
2 Correct 2 ms 200 KB Guessed the password with 92 queries.
3 Correct 1 ms 200 KB Guessed the password with 18 queries.
4 Correct 2 ms 200 KB Guessed the password with 175 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 296 KB Guessed the password with 2758 queries.
2 Correct 66 ms 296 KB Guessed the password with 5083 queries.
3 Correct 48 ms 428 KB Guessed the password with 4586 queries.
4 Correct 103 ms 340 KB Guessed the password with 8128 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 59 queries.
2 Correct 2 ms 200 KB Guessed the password with 100 queries.
3 Correct 1 ms 200 KB Guessed the password with 48 queries.
4 Correct 2 ms 200 KB Guessed the password with 92 queries.
5 Correct 1 ms 200 KB Guessed the password with 18 queries.
6 Correct 2 ms 200 KB Guessed the password with 175 queries.
7 Correct 29 ms 296 KB Guessed the password with 2758 queries.
8 Correct 66 ms 296 KB Guessed the password with 5083 queries.
9 Correct 48 ms 428 KB Guessed the password with 4586 queries.
10 Correct 103 ms 340 KB Guessed the password with 8128 queries.
11 Correct 82 ms 328 KB Guessed the password with 8154 queries.
12 Correct 80 ms 304 KB Guessed the password with 8162 queries.
13 Correct 132 ms 452 KB Guessed the password with 11520 queries.
14 Correct 118 ms 352 KB Guessed the password with 11656 queries.
15 Correct 127 ms 344 KB Guessed the password with 10875 queries.
16 Correct 82 ms 320 KB Guessed the password with 10858 queries.
17 Correct 120 ms 444 KB Guessed the password with 10218 queries.
18 Correct 73 ms 292 KB Guessed the password with 10244 queries.
19 Correct 73 ms 452 KB Guessed the password with 9687 queries.
20 Correct 120 ms 456 KB Guessed the password with 9781 queries.
21 Correct 124 ms 464 KB Guessed the password with 11726 queries.
22 Correct 122 ms 360 KB Guessed the password with 11782 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 59 queries.
2 Correct 2 ms 200 KB Guessed the password with 100 queries.
3 Correct 1 ms 200 KB Guessed the password with 48 queries.
4 Correct 2 ms 200 KB Guessed the password with 92 queries.
5 Correct 1 ms 200 KB Guessed the password with 18 queries.
6 Correct 2 ms 200 KB Guessed the password with 175 queries.
7 Correct 29 ms 296 KB Guessed the password with 2758 queries.
8 Correct 66 ms 296 KB Guessed the password with 5083 queries.
9 Correct 48 ms 428 KB Guessed the password with 4586 queries.
10 Correct 103 ms 340 KB Guessed the password with 8128 queries.
11 Correct 82 ms 328 KB Guessed the password with 8154 queries.
12 Correct 80 ms 304 KB Guessed the password with 8162 queries.
13 Correct 132 ms 452 KB Guessed the password with 11520 queries.
14 Correct 118 ms 352 KB Guessed the password with 11656 queries.
15 Correct 127 ms 344 KB Guessed the password with 10875 queries.
16 Correct 82 ms 320 KB Guessed the password with 10858 queries.
17 Correct 120 ms 444 KB Guessed the password with 10218 queries.
18 Correct 73 ms 292 KB Guessed the password with 10244 queries.
19 Correct 73 ms 452 KB Guessed the password with 9687 queries.
20 Correct 120 ms 456 KB Guessed the password with 9781 queries.
21 Correct 124 ms 464 KB Guessed the password with 11726 queries.
22 Correct 122 ms 360 KB Guessed the password with 11782 queries.
23 Correct 230 ms 468 KB Guessed the password with 23693 queries.
24 Correct 233 ms 432 KB Guessed the password with 20947 queries.
25 Correct 186 ms 508 KB Guessed the password with 23705 queries.
26 Correct 210 ms 476 KB Guessed the password with 19107 queries.
27 Correct 299 ms 500 KB Guessed the password with 23733 queries.
28 Correct 218 ms 548 KB Guessed the password with 16828 queries.
29 Correct 252 ms 496 KB Guessed the password with 23694 queries.
30 Correct 150 ms 360 KB Guessed the password with 14391 queries.