oj.uz

Submission #696286

# Submission time Handle Problem Language Result Execution time Memory
696286 2023-02-06T07:11:56 Z jhwest2 Password (RMI18_password) C++17
80 / 100
 1043 ms 644 KB 
#include <bits/stdc++.h>
using namespace std;

int query(string str);

int n, s, cnt[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);
    }
    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 ask = left;
        int sz = left.size();
        vector<int> num(sz + 1);
        for (int j = 0; j <= sz; j++) {
            string tmp = ask;
            while (tmp.size() < n)
                tmp += 'a' + i;
            num[j] = query(tmp) - ask.size();
            if (j != sz)
                ask.pop_back();
        }
        ask = left;
        left.clear();
        for (int j = sz; j > 0; j--) 
            num[j] -= num[j - 1];
        for (int j = 0; j <= sz; j++) {
            while (num[sz - j]--)
                left += 'a' + i;
            if (j != sz)
                left += ask[j];
        }
    }
    for (int i = s / 2 + 1; i < s; i++) {
        string ask = right;
        int sz = right.size();
        vector<int> num(sz + 1);

        for (int j = 0; j <= sz; j++) {
            string tmp = ask;
            while (tmp.size() < n)
                tmp += 'a' + i;
            num[j] = query(tmp) - ask.size();
            if (j != sz)
                ask.pop_back();
        }
        ask = right;
        right.clear();
        for (int j = sz; j > 0; j--) 
            num[j] -= num[j - 1];
        for (int j = 0; j <= sz; j++) {
            while (num[sz - j]--)
                right += 'a' + i;
            if (j != sz)
                right += ask[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:28:31: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |             while (tmp.size() < n)
      |                    ~~~~~~~~~~~^~~
password.cpp:52:31: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |             while (tmp.size() < n)
      |                    ~~~~~~~~~~~^~~
password.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (int i = 0; i < right.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
password.cpp:72:73: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         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 91 queries.
2 Correct 2 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 220 KB Guessed the password with 48 queries.
2 Correct 1 ms 208 KB Guessed the password with 77 queries.
3 Correct 1 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 42 ms 320 KB Guessed the password with 2821 queries.
2 Correct 59 ms 336 KB Guessed the password with 5681 queries.
3 Correct 83 ms 336 KB Guessed the password with 6298 queries.
4 Correct 212 ms 460 KB Guessed the password with 11728 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 91 queries.
2 Correct 2 ms 208 KB Guessed the password with 187 queries.
3 Correct 1 ms 220 KB Guessed the password with 48 queries.
4 Correct 1 ms 208 KB Guessed the password with 77 queries.
5 Correct 1 ms 208 KB Guessed the password with 95 queries.
6 Correct 2 ms 208 KB Guessed the password with 128 queries.
7 Correct 42 ms 320 KB Guessed the password with 2821 queries.
8 Correct 59 ms 336 KB Guessed the password with 5681 queries.
9 Correct 83 ms 336 KB Guessed the password with 6298 queries.
10 Correct 212 ms 460 KB Guessed the password with 11728 queries.
11 Correct 461 ms 464 KB Guessed the password with 29432 queries.
12 Correct 168 ms 460 KB Guessed the password with 8716 queries.
13 Correct 575 ms 336 KB Guessed the password with 26438 queries.
14 Correct 314 ms 348 KB Guessed the password with 16725 queries.
15 Correct 538 ms 348 KB Guessed the password with 29314 queries.
16 Correct 266 ms 344 KB Guessed the password with 13114 queries.
17 Correct 529 ms 452 KB Guessed the password with 33983 queries.
18 Correct 184 ms 464 KB Guessed the password with 11137 queries.
19 Correct 671 ms 344 KB Guessed the password with 36308 queries.
20 Correct 219 ms 336 KB Guessed the password with 11753 queries.
21 Correct 698 ms 344 KB Guessed the password with 33909 queries.
22 Correct 316 ms 352 KB Guessed the password with 14847 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 91 queries.
2 Correct 2 ms 208 KB Guessed the password with 187 queries.
3 Correct 1 ms 220 KB Guessed the password with 48 queries.
4 Correct 1 ms 208 KB Guessed the password with 77 queries.
5 Correct 1 ms 208 KB Guessed the password with 95 queries.
6 Correct 2 ms 208 KB Guessed the password with 128 queries.
7 Correct 42 ms 320 KB Guessed the password with 2821 queries.
8 Correct 59 ms 336 KB Guessed the password with 5681 queries.
9 Correct 83 ms 336 KB Guessed the password with 6298 queries.
10 Correct 212 ms 460 KB Guessed the password with 11728 queries.
11 Correct 461 ms 464 KB Guessed the password with 29432 queries.
12 Correct 168 ms 460 KB Guessed the password with 8716 queries.
13 Correct 575 ms 336 KB Guessed the password with 26438 queries.
14 Correct 314 ms 348 KB Guessed the password with 16725 queries.
15 Correct 538 ms 348 KB Guessed the password with 29314 queries.
16 Correct 266 ms 344 KB Guessed the password with 13114 queries.
17 Correct 529 ms 452 KB Guessed the password with 33983 queries.
18 Correct 184 ms 464 KB Guessed the password with 11137 queries.
19 Correct 671 ms 344 KB Guessed the password with 36308 queries.
20 Correct 219 ms 336 KB Guessed the password with 11753 queries.
21 Correct 698 ms 344 KB Guessed the password with 33909 queries.
22 Correct 316 ms 352 KB Guessed the password with 14847 queries.
23 Correct 1043 ms 512 KB Guessed the password with 35148 queries.
24 Correct 992 ms 644 KB Guessed the password with 35820 queries.
25 Correct 998 ms 628 KB Guessed the password with 35112 queries.
26 Execution timed out 955 ms 508 KB Time limit exceeded (wall clock)
27 Halted 0 ms 0 KB -