oj.uz

Submission #696291

# Submission time Handle Problem Language Result Execution time Memory
696291 2023-02-06T07:20:49 Z jhwest2 Password (RMI18_password) C++14
80 / 100
 581 ms 592 KB 
#include <bits/stdc++.h>
using namespace std;

int query(string str);

int n, s, cnt[26], num[5050];
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);
    }
    string left, right;
    for (int i = 0; i < cnt[0]; i++)
        left += 'a';
    for (int i = 0; i < cnt[s / 2]; i++)
        right += 'a' + s / 2;

    for (int i = 1; i < s / 2; i++) {
        string str;
        for (int j = 0; j < n; j++)
            str += 'a' + 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' + i;
            if (j != sz)
                left += str[j];
        }
    }
    for (int i = s / 2 + 1; i < s; i++) {
        string str;
        for (int j = 0; j < n; j++)
            str += 'a' + 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' + 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:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (int i = 0; i < right.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
password.cpp:65:73: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         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 2 ms 208 KB Guessed the password with 91 queries.
2 Correct 3 ms 208 KB Guessed the password with 187 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 48 queries.
2 Correct 1 ms 208 KB Guessed the password with 77 queries.
3 Correct 2 ms 208 KB Guessed the password with 95 queries.
4 Correct 2 ms 208 KB Guessed the password with 128 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 428 KB Guessed the password with 2821 queries.
2 Correct 63 ms 324 KB Guessed the password with 5681 queries.
3 Correct 61 ms 328 KB Guessed the password with 6298 queries.
4 Correct 130 ms 328 KB Guessed the password with 11728 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 91 queries.
2 Correct 3 ms 208 KB Guessed the password with 187 queries.
3 Correct 1 ms 208 KB Guessed the password with 48 queries.
4 Correct 1 ms 208 KB Guessed the password with 77 queries.
5 Correct 2 ms 208 KB Guessed the password with 95 queries.
6 Correct 2 ms 208 KB Guessed the password with 128 queries.
7 Correct 23 ms 428 KB Guessed the password with 2821 queries.
8 Correct 63 ms 324 KB Guessed the password with 5681 queries.
9 Correct 61 ms 328 KB Guessed the password with 6298 queries.
10 Correct 130 ms 328 KB Guessed the password with 11728 queries.
11 Correct 261 ms 348 KB Guessed the password with 29432 queries.
12 Correct 59 ms 496 KB Guessed the password with 8716 queries.
13 Correct 265 ms 340 KB Guessed the password with 26438 queries.
14 Correct 124 ms 344 KB Guessed the password with 16725 queries.
15 Correct 216 ms 348 KB Guessed the password with 29314 queries.
16 Correct 150 ms 352 KB Guessed the password with 13114 queries.
17 Correct 294 ms 476 KB Guessed the password with 33983 queries.
18 Correct 116 ms 312 KB Guessed the password with 11137 queries.
19 Correct 303 ms 440 KB Guessed the password with 36308 queries.
20 Correct 76 ms 480 KB Guessed the password with 11753 queries.
21 Correct 332 ms 468 KB Guessed the password with 33909 queries.
22 Correct 164 ms 480 KB Guessed the password with 14847 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 91 queries.
2 Correct 3 ms 208 KB Guessed the password with 187 queries.
3 Correct 1 ms 208 KB Guessed the password with 48 queries.
4 Correct 1 ms 208 KB Guessed the password with 77 queries.
5 Correct 2 ms 208 KB Guessed the password with 95 queries.
6 Correct 2 ms 208 KB Guessed the password with 128 queries.
7 Correct 23 ms 428 KB Guessed the password with 2821 queries.
8 Correct 63 ms 324 KB Guessed the password with 5681 queries.
9 Correct 61 ms 328 KB Guessed the password with 6298 queries.
10 Correct 130 ms 328 KB Guessed the password with 11728 queries.
11 Correct 261 ms 348 KB Guessed the password with 29432 queries.
12 Correct 59 ms 496 KB Guessed the password with 8716 queries.
13 Correct 265 ms 340 KB Guessed the password with 26438 queries.
14 Correct 124 ms 344 KB Guessed the password with 16725 queries.
15 Correct 216 ms 348 KB Guessed the password with 29314 queries.
16 Correct 150 ms 352 KB Guessed the password with 13114 queries.
17 Correct 294 ms 476 KB Guessed the password with 33983 queries.
18 Correct 116 ms 312 KB Guessed the password with 11137 queries.
19 Correct 303 ms 440 KB Guessed the password with 36308 queries.
20 Correct 76 ms 480 KB Guessed the password with 11753 queries.
21 Correct 332 ms 468 KB Guessed the password with 33909 queries.
22 Correct 164 ms 480 KB Guessed the password with 14847 queries.
23 Correct 581 ms 592 KB Guessed the password with 35148 queries.
24 Correct 417 ms 584 KB Guessed the password with 35820 queries.
25 Correct 379 ms 480 KB Guessed the password with 35112 queries.
26 Execution timed out 534 ms 480 KB Time limit exceeded (wall clock)
27 Halted 0 ms 0 KB -