oj.uz

Submission #723242

# Submission time Handle Problem Language Result Execution time Memory
723242 2023-04-13T12:21:22 Z tvladm2009 Password (RMI18_password) C++17
100 / 100
 333 ms 668 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int query(string s);

int N;

string solve(int l, int r) {
    int mid = (l + r) / 2;
    if (l == r) {
        string qry = "";
        for (int j = 1; j <= N; j++) {
            qry += char('a' + l);
        }
        int resp = query(qry);
        string answer = "";
        for (int j = 1; j <= resp; j++) {
            answer += char('a' + l);
        }
        return answer;
    }
    string a = solve(l, mid);
    string b = solve(mid + 1, r);
    string answer = "";
    int posA = 0, posB = 0;
    while (posA < (int) a.size()) {
        while (true) {
            string qry = answer;
            qry += a[posA];
            for (int j = posB; j < (int) b.size(); j++) {
                qry += b[j];
            }
            int resp = query(qry);
            if (resp == (int) b.size() + posA + 1) {
                answer += a[posA];
                break;
            }
            answer += b[posB];
            posB++;
        }
        posA++;
    }
    for (int i = posB; i < (int) b.size(); i++) {
        answer += b[i];
    }
    return answer;
}

string guess(int _N, int S) {
    N = _N;
    string answer = solve(0, S - 1);
    return answer;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 52 queries.
2 Correct 1 ms 208 KB Guessed the password with 127 queries.
3 Correct 1 ms 208 KB Guessed the password with 103 queries.
4 Correct 2 ms 208 KB Guessed the password with 198 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 324 KB Guessed the password with 3484 queries.
2 Correct 55 ms 324 KB Guessed the password with 5106 queries.
3 Correct 86 ms 336 KB Guessed the password with 6586 queries.
4 Correct 62 ms 468 KB Guessed the password with 8782 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 66 queries.
2 Correct 1 ms 208 KB Guessed the password with 118 queries.
3 Correct 1 ms 208 KB Guessed the password with 52 queries.
4 Correct 1 ms 208 KB Guessed the password with 127 queries.
5 Correct 1 ms 208 KB Guessed the password with 103 queries.
6 Correct 2 ms 208 KB Guessed the password with 198 queries.
7 Correct 36 ms 324 KB Guessed the password with 3484 queries.
8 Correct 55 ms 324 KB Guessed the password with 5106 queries.
9 Correct 86 ms 336 KB Guessed the password with 6586 queries.
10 Correct 62 ms 468 KB Guessed the password with 8782 queries.
11 Correct 171 ms 340 KB Guessed the password with 13885 queries.
12 Correct 188 ms 460 KB Guessed the password with 12776 queries.
13 Correct 121 ms 340 KB Guessed the password with 14581 queries.
14 Correct 174 ms 468 KB Guessed the password with 14013 queries.
15 Correct 172 ms 336 KB Guessed the password with 15441 queries.
16 Correct 196 ms 472 KB Guessed the password with 14564 queries.
17 Correct 182 ms 480 KB Guessed the password with 16280 queries.
18 Correct 252 ms 352 KB Guessed the password with 15251 queries.
19 Correct 151 ms 456 KB Guessed the password with 16677 queries.
20 Correct 215 ms 348 KB Guessed the password with 14884 queries.
21 Correct 137 ms 340 KB Guessed the password with 16950 queries.
22 Correct 216 ms 464 KB Guessed the password with 15671 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 66 queries.
2 Correct 1 ms 208 KB Guessed the password with 118 queries.
3 Correct 1 ms 208 KB Guessed the password with 52 queries.
4 Correct 1 ms 208 KB Guessed the password with 127 queries.
5 Correct 1 ms 208 KB Guessed the password with 103 queries.
6 Correct 2 ms 208 KB Guessed the password with 198 queries.
7 Correct 36 ms 324 KB Guessed the password with 3484 queries.
8 Correct 55 ms 324 KB Guessed the password with 5106 queries.
9 Correct 86 ms 336 KB Guessed the password with 6586 queries.
10 Correct 62 ms 468 KB Guessed the password with 8782 queries.
11 Correct 171 ms 340 KB Guessed the password with 13885 queries.
12 Correct 188 ms 460 KB Guessed the password with 12776 queries.
13 Correct 121 ms 340 KB Guessed the password with 14581 queries.
14 Correct 174 ms 468 KB Guessed the password with 14013 queries.
15 Correct 172 ms 336 KB Guessed the password with 15441 queries.
16 Correct 196 ms 472 KB Guessed the password with 14564 queries.
17 Correct 182 ms 480 KB Guessed the password with 16280 queries.
18 Correct 252 ms 352 KB Guessed the password with 15251 queries.
19 Correct 151 ms 456 KB Guessed the password with 16677 queries.
20 Correct 215 ms 348 KB Guessed the password with 14884 queries.
21 Correct 137 ms 340 KB Guessed the password with 16950 queries.
22 Correct 216 ms 464 KB Guessed the password with 15671 queries.
23 Correct 217 ms 548 KB Guessed the password with 23729 queries.
24 Correct 242 ms 668 KB Guessed the password with 22608 queries.
25 Correct 254 ms 380 KB Guessed the password with 23830 queries.
26 Correct 256 ms 456 KB Guessed the password with 24145 queries.
27 Correct 333 ms 592 KB Guessed the password with 23802 queries.
28 Correct 320 ms 436 KB Guessed the password with 24575 queries.
29 Correct 253 ms 472 KB Guessed the password with 23870 queries.
30 Correct 252 ms 580 KB Guessed the password with 23108 queries.