oj.uz

Submission #872942

# Submission time Handle Problem Language Result Execution time Memory
872942 2023-11-14T06:37:28 Z vjudge1 Password (RMI18_password) C++17
100 / 100
 131 ms 2076 KB 
#include <bits/stdc++.h>
using namespace std;
int query(string q);
string guess(int n, int s) {
    set < pair<int, string> > S;
    for(char c = 'a'; c < 'a'+s; c++) {
        string cur;
        for(int i = 0; i < n; i++) cur += c;
        int m = query(cur);
        if(m > 0) {
            cur = "";
            for(int i = 0; i < m; i++) {
                cur += c;
            }
            S.insert({cur.size(), cur});
        }
    }
    while(S.size() > 1) {
        string a = S.begin()->second;
        S.erase(S.begin());
        string b = S.begin()->second;
        S.erase(S.begin());
        string ans = "";
        int j = 0;
        for(int i = 0; i <= a.size(); i++) {
            
            while(j < b.size()) {
                string cur = ans;
                cur += b[j];
                for(int k = i; k < a.size(); k++) {
                    cur += a[k];
                }
                if(query(cur) == cur.size()) {
                    ans+=b[j];
                    j++;
                    continue;
                }
                break;
            }
            if(i < a.size()) ans += a[i];
        } 
        S.insert({ans.size(), ans});
    }
    return S.begin()->second;
}

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:25:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for(int i = 0; i <= a.size(); i++) {
      |                        ~~^~~~~~~~~~~
password.cpp:27:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |             while(j < b.size()) {
      |                   ~~^~~~~~~~~~
password.cpp:30:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |                 for(int k = i; k < a.size(); k++) {
      |                                ~~^~~~~~~~~~
password.cpp:33:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |                 if(query(cur) == cur.size()) {
      |                    ~~~~~~~~~~~^~~~~~~~~~~~~
password.cpp:40:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |             if(i < a.size()) ans += a[i];
      |                ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Guessed the password with 62 queries.
2 Correct 1 ms 344 KB Guessed the password with 121 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Guessed the password with 48 queries.
2 Correct 1 ms 344 KB Guessed the password with 93 queries.
3 Correct 1 ms 344 KB Guessed the password with 91 queries.
4 Correct 1 ms 432 KB Guessed the password with 180 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1220 KB Guessed the password with 2761 queries.
2 Correct 24 ms 952 KB Guessed the password with 5104 queries.
3 Correct 21 ms 952 KB Guessed the password with 4605 queries.
4 Correct 36 ms 960 KB Guessed the password with 8101 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Guessed the password with 62 queries.
2 Correct 1 ms 344 KB Guessed the password with 121 queries.
3 Correct 0 ms 344 KB Guessed the password with 48 queries.
4 Correct 1 ms 344 KB Guessed the password with 93 queries.
5 Correct 1 ms 344 KB Guessed the password with 91 queries.
6 Correct 1 ms 432 KB Guessed the password with 180 queries.
7 Correct 12 ms 1220 KB Guessed the password with 2761 queries.
8 Correct 24 ms 952 KB Guessed the password with 5104 queries.
9 Correct 21 ms 952 KB Guessed the password with 4605 queries.
10 Correct 36 ms 960 KB Guessed the password with 8101 queries.
11 Correct 38 ms 724 KB Guessed the password with 8178 queries.
12 Correct 41 ms 720 KB Guessed the password with 8184 queries.
13 Correct 53 ms 1216 KB Guessed the password with 11549 queries.
14 Correct 53 ms 1220 KB Guessed the password with 11679 queries.
15 Correct 54 ms 720 KB Guessed the password with 10910 queries.
16 Correct 63 ms 956 KB Guessed the password with 10880 queries.
17 Correct 51 ms 980 KB Guessed the password with 10245 queries.
18 Correct 52 ms 492 KB Guessed the password with 10274 queries.
19 Correct 48 ms 732 KB Guessed the password with 9709 queries.
20 Correct 51 ms 960 KB Guessed the password with 9801 queries.
21 Correct 65 ms 968 KB Guessed the password with 11743 queries.
22 Correct 62 ms 960 KB Guessed the password with 11781 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Guessed the password with 62 queries.
2 Correct 1 ms 344 KB Guessed the password with 121 queries.
3 Correct 0 ms 344 KB Guessed the password with 48 queries.
4 Correct 1 ms 344 KB Guessed the password with 93 queries.
5 Correct 1 ms 344 KB Guessed the password with 91 queries.
6 Correct 1 ms 432 KB Guessed the password with 180 queries.
7 Correct 12 ms 1220 KB Guessed the password with 2761 queries.
8 Correct 24 ms 952 KB Guessed the password with 5104 queries.
9 Correct 21 ms 952 KB Guessed the password with 4605 queries.
10 Correct 36 ms 960 KB Guessed the password with 8101 queries.
11 Correct 38 ms 724 KB Guessed the password with 8178 queries.
12 Correct 41 ms 720 KB Guessed the password with 8184 queries.
13 Correct 53 ms 1216 KB Guessed the password with 11549 queries.
14 Correct 53 ms 1220 KB Guessed the password with 11679 queries.
15 Correct 54 ms 720 KB Guessed the password with 10910 queries.
16 Correct 63 ms 956 KB Guessed the password with 10880 queries.
17 Correct 51 ms 980 KB Guessed the password with 10245 queries.
18 Correct 52 ms 492 KB Guessed the password with 10274 queries.
19 Correct 48 ms 732 KB Guessed the password with 9709 queries.
20 Correct 51 ms 960 KB Guessed the password with 9801 queries.
21 Correct 65 ms 968 KB Guessed the password with 11743 queries.
22 Correct 62 ms 960 KB Guessed the password with 11781 queries.
23 Correct 131 ms 2040 KB Guessed the password with 23751 queries.
24 Correct 113 ms 1032 KB Guessed the password with 21005 queries.
25 Correct 126 ms 1316 KB Guessed the password with 23741 queries.
26 Correct 99 ms 1256 KB Guessed the password with 19118 queries.
27 Correct 119 ms 1648 KB Guessed the password with 23712 queries.
28 Correct 89 ms 1516 KB Guessed the password with 16852 queries.
29 Correct 122 ms 1140 KB Guessed the password with 23732 queries.
30 Correct 88 ms 2076 KB Guessed the password with 14420 queries.