oj.uz

Submission #464135

# Submission time Handle Problem Language Result Execution time Memory
464135 2021-08-12T12:39:40 Z Mamedov Password (RMI18_password) C++17
80 / 100
 523 ms 492 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define ui unsigned int
#define pii pair<int, int>
#define piii pair<int, pii>
#define pb push_back
#define f first
#define s second
#define oo (1ll << 60)

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


int query(string str);

string guess(int n, int s) {
    string str;
    vector<pii>countLetter(s);
    for(int i = 0; i < s; ++i) {
        str = "";
        for(int j = 0; j < n; ++j) {
            str += ('a' + i);
        }
        countLetter[i].f = query(str);
        countLetter[i].s = i;
    }
    sort(countLetter.begin(), countLetter.end());
    str = "";
    for(int i = 0; i < countLetter[0].f; ++i) {
        str += ('a' + countLetter[0].s);
    }
    for(int i = 1; i < s; ++i) {
        string add = "";
        for(int j = 0; j < countLetter[i].f; ++j) {
            add += ('a' + countLetter[i].s);
        }
        int len = str.length();
        vector<int>comesAfter(len + 2);
        comesAfter[0] = countLetter[i].f;
        comesAfter[len + 1] = 0;
        for(int j = 1; j <= len; ++j) {
            string ask = str.substr(0, j) + add;
            comesAfter[j] = query(ask) - j;
        }

        for(int j = 0; j <= len; ++j) {
            for(int k = comesAfter[j]; k > comesAfter[j + 1]; --k) {
                str.insert(str.begin() + j + countLetter[i].f - k, 'a' + countLetter[i].s);
            }
        }
    }
    return str;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Guessed the password with 121 queries.
2 Correct 5 ms 200 KB Guessed the password with 277 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 27 queries.
2 Correct 1 ms 200 KB Guessed the password with 32 queries.
3 Correct 1 ms 200 KB Guessed the password with 18 queries.
4 Correct 2 ms 200 KB Guessed the password with 90 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 308 KB Guessed the password with 2149 queries.
2 Correct 112 ms 316 KB Guessed the password with 8435 queries.
3 Correct 21 ms 308 KB Guessed the password with 3621 queries.
4 Correct 85 ms 452 KB Guessed the password with 12042 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Guessed the password with 121 queries.
2 Correct 5 ms 200 KB Guessed the password with 277 queries.
3 Correct 1 ms 200 KB Guessed the password with 27 queries.
4 Correct 1 ms 200 KB Guessed the password with 32 queries.
5 Correct 1 ms 200 KB Guessed the password with 18 queries.
6 Correct 2 ms 200 KB Guessed the password with 90 queries.
7 Correct 20 ms 308 KB Guessed the password with 2149 queries.
8 Correct 112 ms 316 KB Guessed the password with 8435 queries.
9 Correct 21 ms 308 KB Guessed the password with 3621 queries.
10 Correct 85 ms 452 KB Guessed the password with 12042 queries.
11 Correct 88 ms 432 KB Guessed the password with 6623 queries.
12 Correct 90 ms 464 KB Guessed the password with 6656 queries.
13 Correct 183 ms 440 KB Guessed the password with 14982 queries.
14 Correct 240 ms 344 KB Guessed the password with 15360 queries.
15 Correct 113 ms 456 KB Guessed the password with 11294 queries.
16 Correct 102 ms 452 KB Guessed the password with 11198 queries.
17 Correct 100 ms 448 KB Guessed the password with 8953 queries.
18 Correct 113 ms 364 KB Guessed the password with 9035 queries.
19 Correct 78 ms 360 KB Guessed the password with 7612 queries.
20 Correct 96 ms 360 KB Guessed the password with 7835 queries.
21 Correct 160 ms 488 KB Guessed the password with 11804 queries.
22 Correct 117 ms 492 KB Guessed the password with 11922 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Guessed the password with 121 queries.
2 Correct 5 ms 200 KB Guessed the password with 277 queries.
3 Correct 1 ms 200 KB Guessed the password with 27 queries.
4 Correct 1 ms 200 KB Guessed the password with 32 queries.
5 Correct 1 ms 200 KB Guessed the password with 18 queries.
6 Correct 2 ms 200 KB Guessed the password with 90 queries.
7 Correct 20 ms 308 KB Guessed the password with 2149 queries.
8 Correct 112 ms 316 KB Guessed the password with 8435 queries.
9 Correct 21 ms 308 KB Guessed the password with 3621 queries.
10 Correct 85 ms 452 KB Guessed the password with 12042 queries.
11 Correct 88 ms 432 KB Guessed the password with 6623 queries.
12 Correct 90 ms 464 KB Guessed the password with 6656 queries.
13 Correct 183 ms 440 KB Guessed the password with 14982 queries.
14 Correct 240 ms 344 KB Guessed the password with 15360 queries.
15 Correct 113 ms 456 KB Guessed the password with 11294 queries.
16 Correct 102 ms 452 KB Guessed the password with 11198 queries.
17 Correct 100 ms 448 KB Guessed the password with 8953 queries.
18 Correct 113 ms 364 KB Guessed the password with 9035 queries.
19 Correct 78 ms 360 KB Guessed the password with 7612 queries.
20 Correct 96 ms 360 KB Guessed the password with 7835 queries.
21 Correct 160 ms 488 KB Guessed the password with 11804 queries.
22 Correct 117 ms 492 KB Guessed the password with 11922 queries.
23 Incorrect 523 ms 352 KB Could not guess the password with 50000 queries.
24 Halted 0 ms 0 KB -