oj.uz

Submission #918145

# Submission time Handle Problem Language Result Execution time Memory
918145 2024-01-29T13:16:43 Z vjudge1 Password (RMI18_password) C++17
100 / 100
 138 ms 1604 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 340 KB Guessed the password with 83 queries.
2 Correct 1 ms 432 KB Guessed the password with 133 queries.

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1244 KB Guessed the password with 2775 queries.
2 Correct 21 ms 1196 KB Guessed the password with 5093 queries.
3 Correct 22 ms 948 KB Guessed the password with 4609 queries.
4 Correct 32 ms 712 KB Guessed the password with 8166 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Guessed the password with 83 queries.
2 Correct 1 ms 432 KB Guessed the password with 133 queries.
3 Correct 0 ms 344 KB Guessed the password with 53 queries.
4 Correct 1 ms 344 KB Guessed the password with 94 queries.
5 Correct 1 ms 344 KB Guessed the password with 107 queries.
6 Correct 2 ms 348 KB Guessed the password with 182 queries.
7 Correct 13 ms 1244 KB Guessed the password with 2775 queries.
8 Correct 21 ms 1196 KB Guessed the password with 5093 queries.
9 Correct 22 ms 948 KB Guessed the password with 4609 queries.
10 Correct 32 ms 712 KB Guessed the password with 8166 queries.
11 Correct 37 ms 972 KB Guessed the password with 8199 queries.
12 Correct 43 ms 980 KB Guessed the password with 8201 queries.
13 Correct 54 ms 980 KB Guessed the password with 11546 queries.
14 Correct 53 ms 980 KB Guessed the password with 11650 queries.
15 Correct 45 ms 988 KB Guessed the password with 10919 queries.
16 Correct 45 ms 720 KB Guessed the password with 10907 queries.
17 Correct 55 ms 964 KB Guessed the password with 10251 queries.
18 Correct 55 ms 1236 KB Guessed the password with 10317 queries.
19 Correct 48 ms 1248 KB Guessed the password with 9729 queries.
20 Correct 52 ms 1216 KB Guessed the password with 9819 queries.
21 Correct 77 ms 976 KB Guessed the password with 11719 queries.
22 Correct 65 ms 716 KB Guessed the password with 11801 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Guessed the password with 83 queries.
2 Correct 1 ms 432 KB Guessed the password with 133 queries.
3 Correct 0 ms 344 KB Guessed the password with 53 queries.
4 Correct 1 ms 344 KB Guessed the password with 94 queries.
5 Correct 1 ms 344 KB Guessed the password with 107 queries.
6 Correct 2 ms 348 KB Guessed the password with 182 queries.
7 Correct 13 ms 1244 KB Guessed the password with 2775 queries.
8 Correct 21 ms 1196 KB Guessed the password with 5093 queries.
9 Correct 22 ms 948 KB Guessed the password with 4609 queries.
10 Correct 32 ms 712 KB Guessed the password with 8166 queries.
11 Correct 37 ms 972 KB Guessed the password with 8199 queries.
12 Correct 43 ms 980 KB Guessed the password with 8201 queries.
13 Correct 54 ms 980 KB Guessed the password with 11546 queries.
14 Correct 53 ms 980 KB Guessed the password with 11650 queries.
15 Correct 45 ms 988 KB Guessed the password with 10919 queries.
16 Correct 45 ms 720 KB Guessed the password with 10907 queries.
17 Correct 55 ms 964 KB Guessed the password with 10251 queries.
18 Correct 55 ms 1236 KB Guessed the password with 10317 queries.
19 Correct 48 ms 1248 KB Guessed the password with 9729 queries.
20 Correct 52 ms 1216 KB Guessed the password with 9819 queries.
21 Correct 77 ms 976 KB Guessed the password with 11719 queries.
22 Correct 65 ms 716 KB Guessed the password with 11801 queries.
23 Correct 138 ms 1308 KB Guessed the password with 23753 queries.
24 Correct 116 ms 1344 KB Guessed the password with 21017 queries.
25 Correct 125 ms 1420 KB Guessed the password with 23719 queries.
26 Correct 98 ms 1604 KB Guessed the password with 19189 queries.
27 Correct 126 ms 1532 KB Guessed the password with 23798 queries.
28 Correct 81 ms 1540 KB Guessed the password with 16867 queries.
29 Correct 118 ms 1260 KB Guessed the password with 23758 queries.
30 Correct 72 ms 1572 KB Guessed the password with 14427 queries.