oj.uz

Submission #773342

# Submission time Handle Problem Language Result Execution time Memory
773342 2023-07-04T22:51:41 Z aykhn Password (RMI18_password) C++14
100 / 100
 209 ms 600 KB 
#include <bits/stdc++.h>

// author: aykhn

using namespace std;

typedef long long ll;
#define pb push_back
#define ins insert
#define mpr make_pair

int cnt[30];
priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> pq;

int query(string str);

void MERGE(string &a, string &b)
{
    int prev = query(b);

    int i = 0;

    for (int j = 0; j <= b.length() && i < a.length(); j++)
    {
        string tmp = b;
        b.ins(b.begin() + j, a[i]);
        int x = query(b);
        if (x <= prev) b = tmp;
        else prev = x, i++;
    }
}

string guess(int n, int s)
{
    string tmp = "";
    for (int i = 0; i < n; i++)
    {
        tmp.pb('a');
    }
    int prev = 0;

    for (int i = 0; i < s; i++)
    {
        cnt[i] = query(tmp);
        pq.push(mpr(cnt[i], tmp.substr(0, cnt[i])));

        for (int j = 0; j < n; j++) tmp[j]++;
    }

    while (pq.size() > 1)
    {
        string A = pq.top().second;
        pq.pop();
        string B = pq.top().second;
        pq.pop();

        MERGE(A, B);

        pq.push(mpr(B.length(), B));
    }

    return pq.top().second;
}

Compilation message

password.cpp: In function 'void MERGE(std::string&, std::string&)':
password.cpp:23:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (int j = 0; j <= b.length() && i < a.length(); j++)
      |                     ~~^~~~~~~~~~~~~
password.cpp:23:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (int j = 0; j <= b.length() && i < a.length(); j++)
      |                                        ~~^~~~~~~~~~~~
password.cpp: In function 'std::string guess(int, int)':
password.cpp:40:9: warning: unused variable 'prev' [-Wunused-variable]
   40 |     int prev = 0;
      |         ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 83 queries.
2 Correct 2 ms 208 KB Guessed the password with 133 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 53 queries.
2 Correct 2 ms 208 KB Guessed the password with 94 queries.
3 Correct 2 ms 208 KB Guessed the password with 107 queries.
4 Correct 2 ms 208 KB Guessed the password with 182 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 456 KB Guessed the password with 2775 queries.
2 Correct 38 ms 296 KB Guessed the password with 5093 queries.
3 Correct 32 ms 356 KB Guessed the password with 4609 queries.
4 Correct 86 ms 364 KB Guessed the password with 8166 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 83 queries.
2 Correct 2 ms 208 KB Guessed the password with 133 queries.
3 Correct 1 ms 208 KB Guessed the password with 53 queries.
4 Correct 2 ms 208 KB Guessed the password with 94 queries.
5 Correct 2 ms 208 KB Guessed the password with 107 queries.
6 Correct 2 ms 208 KB Guessed the password with 182 queries.
7 Correct 24 ms 456 KB Guessed the password with 2775 queries.
8 Correct 38 ms 296 KB Guessed the password with 5093 queries.
9 Correct 32 ms 356 KB Guessed the password with 4609 queries.
10 Correct 86 ms 364 KB Guessed the password with 8166 queries.
11 Correct 51 ms 484 KB Guessed the password with 8199 queries.
12 Correct 75 ms 300 KB Guessed the password with 8201 queries.
13 Correct 52 ms 360 KB Guessed the password with 11546 queries.
14 Correct 63 ms 300 KB Guessed the password with 11650 queries.
15 Correct 70 ms 364 KB Guessed the password with 10919 queries.
16 Correct 85 ms 600 KB Guessed the password with 10907 queries.
17 Correct 51 ms 368 KB Guessed the password with 10251 queries.
18 Correct 76 ms 364 KB Guessed the password with 10317 queries.
19 Correct 71 ms 360 KB Guessed the password with 9729 queries.
20 Correct 75 ms 456 KB Guessed the password with 9819 queries.
21 Correct 96 ms 376 KB Guessed the password with 11719 queries.
22 Correct 99 ms 372 KB Guessed the password with 11801 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 83 queries.
2 Correct 2 ms 208 KB Guessed the password with 133 queries.
3 Correct 1 ms 208 KB Guessed the password with 53 queries.
4 Correct 2 ms 208 KB Guessed the password with 94 queries.
5 Correct 2 ms 208 KB Guessed the password with 107 queries.
6 Correct 2 ms 208 KB Guessed the password with 182 queries.
7 Correct 24 ms 456 KB Guessed the password with 2775 queries.
8 Correct 38 ms 296 KB Guessed the password with 5093 queries.
9 Correct 32 ms 356 KB Guessed the password with 4609 queries.
10 Correct 86 ms 364 KB Guessed the password with 8166 queries.
11 Correct 51 ms 484 KB Guessed the password with 8199 queries.
12 Correct 75 ms 300 KB Guessed the password with 8201 queries.
13 Correct 52 ms 360 KB Guessed the password with 11546 queries.
14 Correct 63 ms 300 KB Guessed the password with 11650 queries.
15 Correct 70 ms 364 KB Guessed the password with 10919 queries.
16 Correct 85 ms 600 KB Guessed the password with 10907 queries.
17 Correct 51 ms 368 KB Guessed the password with 10251 queries.
18 Correct 76 ms 364 KB Guessed the password with 10317 queries.
19 Correct 71 ms 360 KB Guessed the password with 9729 queries.
20 Correct 75 ms 456 KB Guessed the password with 9819 queries.
21 Correct 96 ms 376 KB Guessed the password with 11719 queries.
22 Correct 99 ms 372 KB Guessed the password with 11801 queries.
23 Correct 209 ms 512 KB Guessed the password with 23753 queries.
24 Correct 164 ms 480 KB Guessed the password with 21017 queries.
25 Correct 175 ms 440 KB Guessed the password with 23719 queries.
26 Correct 165 ms 500 KB Guessed the password with 19189 queries.
27 Correct 204 ms 516 KB Guessed the password with 23798 queries.
28 Correct 96 ms 504 KB Guessed the password with 16867 queries.
29 Correct 181 ms 480 KB Guessed the password with 23758 queries.
30 Correct 129 ms 492 KB Guessed the password with 14427 queries.