oj.uz

Submission #755952

# Submission time Handle Problem Language Result Execution time Memory
755952 2023-06-10T18:25:46 Z MohamedFaresNebili Password (RMI18_password) C++14
80 / 100
 1371 ms 444 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 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 208 KB Guessed the password with 48 queries.
2 Correct 2 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 292 KB Guessed the password with 179 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 336 KB Guessed the password with 3133 queries.
2 Correct 146 ms 444 KB Guessed the password with 9153 queries.
3 Correct 71 ms 300 KB Guessed the password with 5201 queries.
4 Correct 188 ms 444 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 2 ms 208 KB Guessed the password with 187 queries.
3 Correct 1 ms 208 KB Guessed the password with 48 queries.
4 Correct 2 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 292 KB Guessed the password with 179 queries.
7 Correct 39 ms 336 KB Guessed the password with 3133 queries.
8 Correct 146 ms 444 KB Guessed the password with 9153 queries.
9 Correct 71 ms 300 KB Guessed the password with 5201 queries.
10 Correct 188 ms 444 KB Guessed the password with 13851 queries.
11 Correct 141 ms 320 KB Guessed the password with 9347 queries.
12 Correct 176 ms 340 KB Guessed the password with 9404 queries.
13 Correct 358 ms 324 KB Guessed the password with 17813 queries.
14 Correct 312 ms 436 KB Guessed the password with 18089 queries.
15 Correct 237 ms 320 KB Guessed the password with 14445 queries.
16 Correct 267 ms 296 KB Guessed the password with 14324 queries.
17 Correct 270 ms 324 KB Guessed the password with 12187 queries.
18 Correct 269 ms 416 KB Guessed the password with 12216 queries.
19 Correct 263 ms 328 KB Guessed the password with 10933 queries.
20 Correct 268 ms 332 KB Guessed the password with 11169 queries.
21 Correct 323 ms 416 KB Guessed the password with 15075 queries.
22 Correct 299 ms 324 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 2 ms 208 KB Guessed the password with 187 queries.
3 Correct 1 ms 208 KB Guessed the password with 48 queries.
4 Correct 2 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 292 KB Guessed the password with 179 queries.
7 Correct 39 ms 336 KB Guessed the password with 3133 queries.
8 Correct 146 ms 444 KB Guessed the password with 9153 queries.
9 Correct 71 ms 300 KB Guessed the password with 5201 queries.
10 Correct 188 ms 444 KB Guessed the password with 13851 queries.
11 Correct 141 ms 320 KB Guessed the password with 9347 queries.
12 Correct 176 ms 340 KB Guessed the password with 9404 queries.
13 Correct 358 ms 324 KB Guessed the password with 17813 queries.
14 Correct 312 ms 436 KB Guessed the password with 18089 queries.
15 Correct 237 ms 320 KB Guessed the password with 14445 queries.
16 Correct 267 ms 296 KB Guessed the password with 14324 queries.
17 Correct 270 ms 324 KB Guessed the password with 12187 queries.
18 Correct 269 ms 416 KB Guessed the password with 12216 queries.
19 Correct 263 ms 328 KB Guessed the password with 10933 queries.
20 Correct 268 ms 332 KB Guessed the password with 11169 queries.
21 Correct 323 ms 416 KB Guessed the password with 15075 queries.
22 Correct 299 ms 324 KB Guessed the password with 14999 queries.
23 Execution timed out 1371 ms 424 KB Time limit exceeded (wall clock)
24 Halted 0 ms 0 KB -