oj.uz

Submission #755953

# Submission time Handle Problem Language Result Execution time Memory
755953 2023-06-10T18:26:33 Z vjudge1 Password (RMI18_password) C++17
80 / 100
 1296 ms 584 KB 
#include <bits/stdc++.h>
 
        using namespace std;
 
        int query(string str);
 
        string guess(int n, int s) {
            string S(n, 'a');
            int freq[s]{0};
            vector<pair<int, int>> v;
            for(int l = 0; l < s; l++) {
                for(int i = 0; i < n; i++)
                    S[i] = char('a' + l);
                freq[l] = query(S);
                v.push_back({freq[l], l});
            }
            sort(v.begin(), v.end());
            S = "";
            for(int l = 0; l < v[0].first; l++)
                S += char('a' + v[0].second);
            for(int _ = 1; _ < s; _++) {
                int l = v[_].second;
                for(int i = 0, last = 0; i < freq[l]; i++) {
                    for(;; last++) {
                        string str = "";
                        for(int e = 0; e < last; e++) str.push_back(S[e]);
                        str.push_back(char('a' + l));
                        for(int e = last; e < S.size(); e++)
                            str.push_back(S[e]);
                        if(query(str) == str.size()) {
                            S = str; last++; break;
                        }
                    }
                }
            }
            return S;
        }

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:28:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |                         for(int e = last; e < S.size(); e++)
      |                                           ~~^~~~~~~~~~
password.cpp:30:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |                         if(query(str) == str.size()) {
      |                            ~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 76 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 93 queries.
3 Correct 2 ms 208 KB Guessed the password with 91 queries.
4 Correct 3 ms 284 KB Guessed the password with 179 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 424 KB Guessed the password with 3133 queries.
2 Correct 135 ms 424 KB Guessed the password with 9153 queries.
3 Correct 82 ms 304 KB Guessed the password with 5201 queries.
4 Correct 205 ms 436 KB Guessed the password with 13851 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 76 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 93 queries.
5 Correct 2 ms 208 KB Guessed the password with 91 queries.
6 Correct 3 ms 284 KB Guessed the password with 179 queries.
7 Correct 48 ms 424 KB Guessed the password with 3133 queries.
8 Correct 135 ms 424 KB Guessed the password with 9153 queries.
9 Correct 82 ms 304 KB Guessed the password with 5201 queries.
10 Correct 205 ms 436 KB Guessed the password with 13851 queries.
11 Correct 189 ms 320 KB Guessed the password with 9347 queries.
12 Correct 155 ms 428 KB Guessed the password with 9404 queries.
13 Correct 294 ms 320 KB Guessed the password with 17813 queries.
14 Correct 318 ms 448 KB Guessed the password with 18089 queries.
15 Correct 243 ms 416 KB Guessed the password with 14445 queries.
16 Correct 277 ms 320 KB Guessed the password with 14324 queries.
17 Correct 221 ms 436 KB Guessed the password with 12187 queries.
18 Correct 220 ms 324 KB Guessed the password with 12216 queries.
19 Correct 222 ms 324 KB Guessed the password with 10933 queries.
20 Correct 221 ms 324 KB Guessed the password with 11169 queries.
21 Correct 363 ms 328 KB Guessed the password with 15075 queries.
22 Correct 261 ms 432 KB Guessed the password with 14999 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 76 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 93 queries.
5 Correct 2 ms 208 KB Guessed the password with 91 queries.
6 Correct 3 ms 284 KB Guessed the password with 179 queries.
7 Correct 48 ms 424 KB Guessed the password with 3133 queries.
8 Correct 135 ms 424 KB Guessed the password with 9153 queries.
9 Correct 82 ms 304 KB Guessed the password with 5201 queries.
10 Correct 205 ms 436 KB Guessed the password with 13851 queries.
11 Correct 189 ms 320 KB Guessed the password with 9347 queries.
12 Correct 155 ms 428 KB Guessed the password with 9404 queries.
13 Correct 294 ms 320 KB Guessed the password with 17813 queries.
14 Correct 318 ms 448 KB Guessed the password with 18089 queries.
15 Correct 243 ms 416 KB Guessed the password with 14445 queries.
16 Correct 277 ms 320 KB Guessed the password with 14324 queries.
17 Correct 221 ms 436 KB Guessed the password with 12187 queries.
18 Correct 220 ms 324 KB Guessed the password with 12216 queries.
19 Correct 222 ms 324 KB Guessed the password with 10933 queries.
20 Correct 221 ms 324 KB Guessed the password with 11169 queries.
21 Correct 363 ms 328 KB Guessed the password with 15075 queries.
22 Correct 261 ms 432 KB Guessed the password with 14999 queries.
23 Execution timed out 1296 ms 584 KB Time limit exceeded (wall clock)
24 Halted 0 ms 0 KB -