oj.uz

Submission #333361

# Submission time Handle Problem Language Result Execution time Memory
333361 2020-12-05T17:24:15 Z valerikk Password (RMI18_password) C++17
100 / 100
 413 ms 812 KB 
#include <bits/stdc++.h>
using namespace std;

int query(string str);

string pushs(string s, char x) {
    s.push_back(x);
    return s;
}

string inserts(string s, int pos, char x) {
    s.insert(s.begin() + pos, x);
    return s;
}

string go(int l, int r) {
    if (r - l == 1) {
        string s = "";
        char x = 'a' + l;
        while (query(pushs(s, x)) == s.size() + 1) s.push_back(x);
        return s;
    }
    int mid = (l + r) / 2;
    auto s = go(l, mid), t = go(mid, r);
    for (int i = 0, j = 0; i <= s.size() && j < t.size(); i++) {
        string kek = inserts(s, i, t[j]);
        if (query(kek) == kek.size()) {
            s = kek;
            j++;
        }
    }
    return s;
}

string guess(int n, int s) {
    return go(0, s);
}

Compilation message

password.cpp: In function 'std::string go(int, int)':
password.cpp:20:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         while (query(pushs(s, x)) == s.size() + 1) s.push_back(x);
      |                ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
password.cpp:25:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for (int i = 0, j = 0; i <= s.size() && j < t.size(); i++) {
      |                            ~~^~~~~~~~~~~
password.cpp:25:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for (int i = 0, j = 0; i <= s.size() && j < t.size(); i++) {
      |                                             ~~^~~~~~~~~~
password.cpp:27:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         if (query(kek) == kek.size()) {
      |             ~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 98 queries.
2 Correct 2 ms 364 KB Guessed the password with 160 queries.
3 Correct 3 ms 364 KB Guessed the password with 261 queries.
4 Correct 2 ms 364 KB Guessed the password with 303 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 396 KB Guessed the password with 4807 queries.
2 Correct 51 ms 492 KB Guessed the password with 6357 queries.
3 Correct 81 ms 636 KB Guessed the password with 8760 queries.
4 Correct 112 ms 628 KB Guessed the password with 10924 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 82 queries.
2 Correct 2 ms 364 KB Guessed the password with 142 queries.
3 Correct 1 ms 364 KB Guessed the password with 98 queries.
4 Correct 2 ms 364 KB Guessed the password with 160 queries.
5 Correct 3 ms 364 KB Guessed the password with 261 queries.
6 Correct 2 ms 364 KB Guessed the password with 303 queries.
7 Correct 42 ms 396 KB Guessed the password with 4807 queries.
8 Correct 51 ms 492 KB Guessed the password with 6357 queries.
9 Correct 81 ms 636 KB Guessed the password with 8760 queries.
10 Correct 112 ms 628 KB Guessed the password with 10924 queries.
11 Correct 169 ms 620 KB Guessed the password with 15574 queries.
12 Correct 173 ms 552 KB Guessed the password with 16731 queries.
13 Correct 156 ms 620 KB Guessed the password with 17054 queries.
14 Correct 200 ms 748 KB Guessed the password with 17481 queries.
15 Correct 181 ms 364 KB Guessed the password with 17822 queries.
16 Correct 141 ms 784 KB Guessed the password with 18805 queries.
17 Correct 160 ms 676 KB Guessed the password with 18371 queries.
18 Correct 159 ms 432 KB Guessed the password with 19776 queries.
19 Correct 173 ms 492 KB Guessed the password with 18580 queries.
20 Correct 195 ms 688 KB Guessed the password with 20058 queries.
21 Correct 240 ms 620 KB Guessed the password with 19725 queries.
22 Correct 223 ms 636 KB Guessed the password with 20455 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 82 queries.
2 Correct 2 ms 364 KB Guessed the password with 142 queries.
3 Correct 1 ms 364 KB Guessed the password with 98 queries.
4 Correct 2 ms 364 KB Guessed the password with 160 queries.
5 Correct 3 ms 364 KB Guessed the password with 261 queries.
6 Correct 2 ms 364 KB Guessed the password with 303 queries.
7 Correct 42 ms 396 KB Guessed the password with 4807 queries.
8 Correct 51 ms 492 KB Guessed the password with 6357 queries.
9 Correct 81 ms 636 KB Guessed the password with 8760 queries.
10 Correct 112 ms 628 KB Guessed the password with 10924 queries.
11 Correct 169 ms 620 KB Guessed the password with 15574 queries.
12 Correct 173 ms 552 KB Guessed the password with 16731 queries.
13 Correct 156 ms 620 KB Guessed the password with 17054 queries.
14 Correct 200 ms 748 KB Guessed the password with 17481 queries.
15 Correct 181 ms 364 KB Guessed the password with 17822 queries.
16 Correct 141 ms 784 KB Guessed the password with 18805 queries.
17 Correct 160 ms 676 KB Guessed the password with 18371 queries.
18 Correct 159 ms 432 KB Guessed the password with 19776 queries.
19 Correct 173 ms 492 KB Guessed the password with 18580 queries.
20 Correct 195 ms 688 KB Guessed the password with 20058 queries.
21 Correct 240 ms 620 KB Guessed the password with 19725 queries.
22 Correct 223 ms 636 KB Guessed the password with 20455 queries.
23 Correct 358 ms 680 KB Guessed the password with 28795 queries.
24 Correct 255 ms 564 KB Guessed the password with 28130 queries.
25 Correct 319 ms 588 KB Guessed the password with 28837 queries.
26 Correct 345 ms 812 KB Guessed the password with 28538 queries.
27 Correct 413 ms 440 KB Guessed the password with 28858 queries.
28 Correct 262 ms 784 KB Guessed the password with 28483 queries.
29 Correct 329 ms 756 KB Guessed the password with 28835 queries.
30 Correct 243 ms 664 KB Guessed the password with 27180 queries.