oj.uz

Submission #331745

# Submission time Handle Problem Language Result Execution time Memory
331745 2020-11-29T21:26:41 Z dolphingarlic Password (RMI18_password) C++14
100 / 100
 283 ms 888 KB 
#include <string>
using namespace std;

extern int query(string str);

string solve(int l, int r, int n) {
    if (l == r) {
        string to_guess = "";
        for (int i = 0; i < n; i++) to_guess += 'a' + l;
        int len = query(to_guess);
        return string(len, 'a' + l);
    } else {
        int mid = (l + r) / 2;
        string a = solve(l, mid, n), b = solve(mid + 1, r, n);
        int a_ptr = 0, b_ptr = 0;
        string known = "";
        while (a_ptr < a.size() && b_ptr < b.size()) {
            string to_guess = known + a[a_ptr] + b.substr(b_ptr);
            int prev_len = known.size() + b.size() - b_ptr;
            if (query(to_guess) > prev_len) known += a[a_ptr++];
            else known += b[b_ptr++];
        }
        if (a_ptr < a.size()) known += a.substr(a_ptr);
        else known += b.substr(b_ptr);
        return known;
    }
}

string guess(int n, int s) { return solve(0, s - 1, n); }

Compilation message

password.cpp: In function 'std::string solve(int, int, int)':
password.cpp:17:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         while (a_ptr < a.size() && b_ptr < b.size()) {
      |                ~~~~~~^~~~~~~~~~
password.cpp:17:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         while (a_ptr < a.size() && b_ptr < b.size()) {
      |                                    ~~~~~~^~~~~~~~~~
password.cpp:23:19: 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 (a_ptr < a.size()) known += a.substr(a_ptr);
      |             ~~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 61 queries.
2 Correct 1 ms 364 KB Guessed the password with 101 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 49 queries.
2 Correct 2 ms 364 KB Guessed the password with 117 queries.
3 Correct 1 ms 364 KB Guessed the password with 92 queries.
4 Correct 3 ms 364 KB Guessed the password with 197 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 380 KB Guessed the password with 3456 queries.
2 Correct 31 ms 644 KB Guessed the password with 5025 queries.
3 Correct 81 ms 492 KB Guessed the password with 6352 queries.
4 Correct 74 ms 620 KB Guessed the password with 8693 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 61 queries.
2 Correct 1 ms 364 KB Guessed the password with 101 queries.
3 Correct 1 ms 364 KB Guessed the password with 49 queries.
4 Correct 2 ms 364 KB Guessed the password with 117 queries.
5 Correct 1 ms 364 KB Guessed the password with 92 queries.
6 Correct 3 ms 364 KB Guessed the password with 197 queries.
7 Correct 22 ms 380 KB Guessed the password with 3456 queries.
8 Correct 31 ms 644 KB Guessed the password with 5025 queries.
9 Correct 81 ms 492 KB Guessed the password with 6352 queries.
10 Correct 74 ms 620 KB Guessed the password with 8693 queries.
11 Correct 175 ms 364 KB Guessed the password with 13638 queries.
12 Correct 140 ms 396 KB Guessed the password with 12459 queries.
13 Correct 101 ms 516 KB Guessed the password with 14392 queries.
14 Correct 166 ms 492 KB Guessed the password with 13937 queries.
15 Correct 109 ms 624 KB Guessed the password with 15073 queries.
16 Correct 152 ms 620 KB Guessed the password with 14154 queries.
17 Correct 184 ms 504 KB Guessed the password with 16054 queries.
18 Correct 188 ms 620 KB Guessed the password with 15189 queries.
19 Correct 151 ms 492 KB Guessed the password with 16410 queries.
20 Correct 136 ms 496 KB Guessed the password with 14247 queries.
21 Correct 135 ms 752 KB Guessed the password with 16849 queries.
22 Correct 150 ms 568 KB Guessed the password with 15315 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 61 queries.
2 Correct 1 ms 364 KB Guessed the password with 101 queries.
3 Correct 1 ms 364 KB Guessed the password with 49 queries.
4 Correct 2 ms 364 KB Guessed the password with 117 queries.
5 Correct 1 ms 364 KB Guessed the password with 92 queries.
6 Correct 3 ms 364 KB Guessed the password with 197 queries.
7 Correct 22 ms 380 KB Guessed the password with 3456 queries.
8 Correct 31 ms 644 KB Guessed the password with 5025 queries.
9 Correct 81 ms 492 KB Guessed the password with 6352 queries.
10 Correct 74 ms 620 KB Guessed the password with 8693 queries.
11 Correct 175 ms 364 KB Guessed the password with 13638 queries.
12 Correct 140 ms 396 KB Guessed the password with 12459 queries.
13 Correct 101 ms 516 KB Guessed the password with 14392 queries.
14 Correct 166 ms 492 KB Guessed the password with 13937 queries.
15 Correct 109 ms 624 KB Guessed the password with 15073 queries.
16 Correct 152 ms 620 KB Guessed the password with 14154 queries.
17 Correct 184 ms 504 KB Guessed the password with 16054 queries.
18 Correct 188 ms 620 KB Guessed the password with 15189 queries.
19 Correct 151 ms 492 KB Guessed the password with 16410 queries.
20 Correct 136 ms 496 KB Guessed the password with 14247 queries.
21 Correct 135 ms 752 KB Guessed the password with 16849 queries.
22 Correct 150 ms 568 KB Guessed the password with 15315 queries.
23 Correct 192 ms 696 KB Guessed the password with 23612 queries.
24 Correct 196 ms 668 KB Guessed the password with 22226 queries.
25 Correct 253 ms 684 KB Guessed the password with 23794 queries.
26 Correct 227 ms 784 KB Guessed the password with 23332 queries.
27 Correct 283 ms 888 KB Guessed the password with 23763 queries.
28 Correct 231 ms 840 KB Guessed the password with 23045 queries.
29 Correct 258 ms 592 KB Guessed the password with 23847 queries.
30 Correct 270 ms 668 KB Guessed the password with 22506 queries.