oj.uz

Submission #696295

# Submission time Handle Problem Language Result Execution time Memory
696295 2023-02-06T07:25:45 Z jhwest2 Password (RMI18_password) C++14
100 / 100
 516 ms 644 KB 
#include <bits/stdc++.h>
using namespace std;

int query(string str);

int n, s, cnt[26], num[5050], w[26];
string guess(int _n, int _s) {
    n = _n; s = _s;

    for (int i = 0; i < s; i++) {
        string str;
        for (int j = 0; j < n; j++)
            str += 'a' + i;
        cnt[i] = query(str);
    }
    for (int i = 0; i < s; i++)
        w[i] = i;

    sort(w, w + s, [&](auto i, auto j) {
        return cnt[i] < cnt[j];
        });

    string left, right;
    for (int i = 0; i < s / 2; i++) {
        string str;
        for (int j = 0; j < n; j++)
            str += 'a' + w[i];

        int sz = left.size();
        for (int j = 0; j <= sz; j++)
            num[j] = query(left.substr(0, sz - j) + str.substr(0, n - sz + j)) - sz + j;
        for (int j = sz; j > 0; j--) 
            num[j] -= num[j - 1];

        str = left;
        left.clear();
        for (int j = 0; j <= sz; j++) {
            while (num[sz - j]--)
                left += 'a' + w[i];
            if (j != sz)
                left += str[j];
        }
    }
    for (int i = s / 2; i < s; i++) {
        string str;
        for (int j = 0; j < n; j++)
            str += 'a' + w[i];

        int sz = right.size();
        for (int j = 0; j <= sz; j++)
            num[j] = query(right.substr(0, sz - j) + str.substr(0, n - sz + j)) - sz + j;
        for (int j = sz; j > 0; j--) 
            num[j] -= num[j - 1];

        str = right;
        right.clear();
        for (int j = 0; j <= sz; j++) {
            while (num[sz - j]--)
                right += 'a' + w[i];
            if (j != sz)
                right += str[j];
        }
    }
    string ans;
    int sz = left.size(), p = 0;
    for (int i = 0; i < right.size(); i++) {
        while (p < sz && query(ans + right[i] + left.substr(p, sz - p)) != ans.size() + 1 + sz - p) {
            ans += left[p++];
        }
        ans += right[i];        
    }
    while (p < sz)
        ans += left[p++];
    return ans;
}

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i = 0; i < right.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
password.cpp:67:73: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         while (p < sz && query(ans + right[i] + left.substr(p, sz - p)) != ans.size() + 1 + sz - p) {
      |                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 50 queries.
2 Correct 1 ms 208 KB Guessed the password with 90 queries.
3 Correct 1 ms 208 KB Guessed the password with 104 queries.
4 Correct 2 ms 208 KB Guessed the password with 148 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 324 KB Guessed the password with 2877 queries.
2 Correct 54 ms 332 KB Guessed the password with 5429 queries.
3 Correct 54 ms 304 KB Guessed the password with 4968 queries.
4 Correct 92 ms 456 KB Guessed the password with 9329 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 93 queries.
2 Correct 2 ms 208 KB Guessed the password with 190 queries.
3 Correct 1 ms 208 KB Guessed the password with 50 queries.
4 Correct 1 ms 208 KB Guessed the password with 90 queries.
5 Correct 1 ms 208 KB Guessed the password with 104 queries.
6 Correct 2 ms 208 KB Guessed the password with 148 queries.
7 Correct 33 ms 324 KB Guessed the password with 2877 queries.
8 Correct 54 ms 332 KB Guessed the password with 5429 queries.
9 Correct 54 ms 304 KB Guessed the password with 4968 queries.
10 Correct 92 ms 456 KB Guessed the password with 9329 queries.
11 Correct 73 ms 472 KB Guessed the password with 9274 queries.
12 Correct 100 ms 348 KB Guessed the password with 9211 queries.
13 Correct 131 ms 452 KB Guessed the password with 15744 queries.
14 Correct 154 ms 348 KB Guessed the password with 15870 queries.
15 Correct 104 ms 456 KB Guessed the password with 14012 queries.
16 Correct 110 ms 568 KB Guessed the password with 13894 queries.
17 Correct 128 ms 460 KB Guessed the password with 11951 queries.
18 Correct 107 ms 476 KB Guessed the password with 12135 queries.
19 Correct 122 ms 468 KB Guessed the password with 10710 queries.
20 Correct 70 ms 428 KB Guessed the password with 9961 queries.
21 Correct 119 ms 484 KB Guessed the password with 14913 queries.
22 Correct 115 ms 604 KB Guessed the password with 14531 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 93 queries.
2 Correct 2 ms 208 KB Guessed the password with 190 queries.
3 Correct 1 ms 208 KB Guessed the password with 50 queries.
4 Correct 1 ms 208 KB Guessed the password with 90 queries.
5 Correct 1 ms 208 KB Guessed the password with 104 queries.
6 Correct 2 ms 208 KB Guessed the password with 148 queries.
7 Correct 33 ms 324 KB Guessed the password with 2877 queries.
8 Correct 54 ms 332 KB Guessed the password with 5429 queries.
9 Correct 54 ms 304 KB Guessed the password with 4968 queries.
10 Correct 92 ms 456 KB Guessed the password with 9329 queries.
11 Correct 73 ms 472 KB Guessed the password with 9274 queries.
12 Correct 100 ms 348 KB Guessed the password with 9211 queries.
13 Correct 131 ms 452 KB Guessed the password with 15744 queries.
14 Correct 154 ms 348 KB Guessed the password with 15870 queries.
15 Correct 104 ms 456 KB Guessed the password with 14012 queries.
16 Correct 110 ms 568 KB Guessed the password with 13894 queries.
17 Correct 128 ms 460 KB Guessed the password with 11951 queries.
18 Correct 107 ms 476 KB Guessed the password with 12135 queries.
19 Correct 122 ms 468 KB Guessed the password with 10710 queries.
20 Correct 70 ms 428 KB Guessed the password with 9961 queries.
21 Correct 119 ms 484 KB Guessed the password with 14913 queries.
22 Correct 115 ms 604 KB Guessed the password with 14531 queries.
23 Correct 372 ms 492 KB Guessed the password with 34386 queries.
24 Correct 326 ms 644 KB Guessed the password with 28697 queries.
25 Correct 296 ms 628 KB Guessed the password with 34354 queries.
26 Correct 300 ms 488 KB Guessed the password with 26045 queries.
27 Correct 516 ms 456 KB Guessed the password with 34453 queries.
28 Correct 261 ms 380 KB Guessed the password with 21421 queries.
29 Correct 224 ms 372 KB Guessed the password with 34233 queries.
30 Correct 225 ms 380 KB Guessed the password with 15940 queries.