oj.uz

Submission #464131

# Submission time Handle Problem Language Result Execution time Memory
464131 2021-08-12T12:31:10 Z Mamedov Password (RMI18_password) C++17
50 / 100
 378 ms 448 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<int>countLetter(s);
    int maxLetter = 0;
    for(int i = 0; i < s; ++i) {
        str = "";
        for(int j = 0; j < n; ++j) {
            str += ('a' + i);
        }
        countLetter[i] = query(str);
        if(countLetter[i] > countLetter[maxLetter]) {
            maxLetter = i;
        }
    }
    str = "";
    for(int i = 0; i < countLetter[maxLetter]; ++i) {
        str += ('a' + maxLetter);
    }
    for(int i = 0; i < s; ++i) {
        if(i == maxLetter) continue;
        string add = "";
        for(int j = 0; j < countLetter[i]; ++j) {
            add += ('a' + i);
        }
        int len = str.length();
        vector<int>comesAfter(len + 2);
        comesAfter[0] = countLetter[i];
        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] - k, 'a' + i);
            }
        }
    }
    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 4 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 29 queries.
2 Correct 1 ms 200 KB Guessed the password with 106 queries.
3 Correct 3 ms 200 KB Guessed the password with 169 queries.
4 Correct 2 ms 200 KB Guessed the password with 170 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 428 KB Guessed the password with 4706 queries.
2 Correct 117 ms 444 KB Guessed the password with 9550 queries.
3 Correct 111 ms 436 KB Guessed the password with 15206 queries.
4 Correct 146 ms 448 KB Guessed the password with 19286 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Guessed the password with 121 queries.
2 Correct 4 ms 200 KB Guessed the password with 277 queries.
3 Correct 1 ms 200 KB Guessed the password with 29 queries.
4 Correct 1 ms 200 KB Guessed the password with 106 queries.
5 Correct 3 ms 200 KB Guessed the password with 169 queries.
6 Correct 2 ms 200 KB Guessed the password with 170 queries.
7 Correct 59 ms 428 KB Guessed the password with 4706 queries.
8 Correct 117 ms 444 KB Guessed the password with 9550 queries.
9 Correct 111 ms 436 KB Guessed the password with 15206 queries.
10 Correct 146 ms 448 KB Guessed the password with 19286 queries.
11 Incorrect 378 ms 360 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -

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 4 ms 200 KB Guessed the password with 277 queries.
3 Correct 1 ms 200 KB Guessed the password with 29 queries.
4 Correct 1 ms 200 KB Guessed the password with 106 queries.
5 Correct 3 ms 200 KB Guessed the password with 169 queries.
6 Correct 2 ms 200 KB Guessed the password with 170 queries.
7 Correct 59 ms 428 KB Guessed the password with 4706 queries.
8 Correct 117 ms 444 KB Guessed the password with 9550 queries.
9 Correct 111 ms 436 KB Guessed the password with 15206 queries.
10 Correct 146 ms 448 KB Guessed the password with 19286 queries.
11 Incorrect 378 ms 360 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -