oj.uz

Submission #848820

# Submission time Handle Problem Language Result Execution time Memory
848820 2023-09-13T14:23:51 Z TahirAliyev Password (RMI18_password) C++17
100 / 100
 124 ms 2016 KB 
#include <bits/stdc++.h>

using namespace std;

int query(string str);

string a, q;
vector<string> v;

string merge(string s1, string s2){
    int p1 = 0, p2 = 0;
    while(p1 < s1.size() && p2 < s2.size()){
        q = s1;
        q.insert(q.begin() + p1, s2[p2]);
        if(query(q) == q.size()){
            s1 = q;
            p2++;
        }
        p1++;
    }
    for(int i = p2; i < s2.size(); i++){
        s1 += s2[i];
    }
    return s1;
}

bool comp(string& a, string& b){
    return a.size() > b.size();
}

string guess(int n, int s){
    for(char c = 'a'; c <= 'a' + s - 1; c++){
        a = "";
        for(int i = 1; i <= n; i++){
            a += c;
        }
        int cnt = query(a);
        if(cnt == 0) continue;
        a = "";
        for(int i = 1; i <= cnt; i++){
            a += c;
        }
        v.push_back(a);
    }
    sort(v.begin(), v.end(), comp);
    while(v.size() > 1){
        a = merge(v[v.size() - 1], v[v.size() - 2]);
        v.pop_back();
        v.pop_back();
        v.push_back(a);
        sort(v.begin(), v.end(), comp);
    }
    return v[0];
}

Compilation message

password.cpp: In function 'std::string merge(std::string, std::string)':
password.cpp:12:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     while(p1 < s1.size() && p2 < s2.size()){
      |           ~~~^~~~~~~~~~~
password.cpp:12:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     while(p1 < s1.size() && p2 < s2.size()){
      |                             ~~~^~~~~~~~~~~
password.cpp:15:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |         if(query(q) == q.size()){
      |            ~~~~~~~~~^~~~~~~~~~~
password.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i = p2; i < s2.size(); i++){
      |                     ~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 688 KB Guessed the password with 2751 queries.
2 Correct 20 ms 688 KB Guessed the password with 5071 queries.
3 Correct 20 ms 952 KB Guessed the password with 4586 queries.
4 Correct 43 ms 968 KB Guessed the password with 8085 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Guessed the password with 56 queries.
2 Correct 1 ms 436 KB Guessed the password with 105 queries.
3 Correct 1 ms 344 KB Guessed the password with 48 queries.
4 Correct 1 ms 344 KB Guessed the password with 91 queries.
5 Correct 1 ms 344 KB Guessed the password with 91 queries.
6 Correct 1 ms 344 KB Guessed the password with 179 queries.
7 Correct 11 ms 688 KB Guessed the password with 2751 queries.
8 Correct 20 ms 688 KB Guessed the password with 5071 queries.
9 Correct 20 ms 952 KB Guessed the password with 4586 queries.
10 Correct 43 ms 968 KB Guessed the password with 8085 queries.
11 Correct 39 ms 964 KB Guessed the password with 8159 queries.
12 Correct 39 ms 480 KB Guessed the password with 8159 queries.
13 Correct 55 ms 980 KB Guessed the password with 11503 queries.
14 Correct 51 ms 1224 KB Guessed the password with 11603 queries.
15 Correct 53 ms 1224 KB Guessed the password with 10883 queries.
16 Correct 54 ms 732 KB Guessed the password with 10858 queries.
17 Correct 42 ms 1236 KB Guessed the password with 10210 queries.
18 Correct 49 ms 984 KB Guessed the password with 10243 queries.
19 Correct 43 ms 1720 KB Guessed the password with 9684 queries.
20 Correct 48 ms 980 KB Guessed the password with 9779 queries.
21 Correct 56 ms 736 KB Guessed the password with 11640 queries.
22 Correct 54 ms 736 KB Guessed the password with 11707 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Guessed the password with 56 queries.
2 Correct 1 ms 436 KB Guessed the password with 105 queries.
3 Correct 1 ms 344 KB Guessed the password with 48 queries.
4 Correct 1 ms 344 KB Guessed the password with 91 queries.
5 Correct 1 ms 344 KB Guessed the password with 91 queries.
6 Correct 1 ms 344 KB Guessed the password with 179 queries.
7 Correct 11 ms 688 KB Guessed the password with 2751 queries.
8 Correct 20 ms 688 KB Guessed the password with 5071 queries.
9 Correct 20 ms 952 KB Guessed the password with 4586 queries.
10 Correct 43 ms 968 KB Guessed the password with 8085 queries.
11 Correct 39 ms 964 KB Guessed the password with 8159 queries.
12 Correct 39 ms 480 KB Guessed the password with 8159 queries.
13 Correct 55 ms 980 KB Guessed the password with 11503 queries.
14 Correct 51 ms 1224 KB Guessed the password with 11603 queries.
15 Correct 53 ms 1224 KB Guessed the password with 10883 queries.
16 Correct 54 ms 732 KB Guessed the password with 10858 queries.
17 Correct 42 ms 1236 KB Guessed the password with 10210 queries.
18 Correct 49 ms 984 KB Guessed the password with 10243 queries.
19 Correct 43 ms 1720 KB Guessed the password with 9684 queries.
20 Correct 48 ms 980 KB Guessed the password with 9779 queries.
21 Correct 56 ms 736 KB Guessed the password with 11640 queries.
22 Correct 54 ms 736 KB Guessed the password with 11707 queries.
23 Correct 124 ms 1352 KB Guessed the password with 23648 queries.
24 Correct 108 ms 1816 KB Guessed the password with 20966 queries.
25 Correct 111 ms 1760 KB Guessed the password with 23670 queries.
26 Correct 88 ms 2016 KB Guessed the password with 19098 queries.
27 Correct 111 ms 1588 KB Guessed the password with 23698 queries.
28 Correct 83 ms 1584 KB Guessed the password with 16823 queries.
29 Correct 122 ms 1332 KB Guessed the password with 23708 queries.
30 Correct 73 ms 1628 KB Guessed the password with 14393 queries.