oj.uz

Submission #918050

# Submission time Handle Problem Language Result Execution time Memory
918050 2024-01-29T12:52:33 Z vjudge1 Password (RMI18_password) C++17
100 / 100
 111 ms 1720 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 1 ms 344 KB Guessed the password with 56 queries.
2 Correct 1 ms 432 KB Guessed the password with 105 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 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 13 ms 1204 KB Guessed the password with 2751 queries.
2 Correct 20 ms 720 KB Guessed the password with 5071 queries.
3 Correct 20 ms 720 KB Guessed the password with 4586 queries.
4 Correct 41 ms 716 KB Guessed the password with 8085 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 56 queries.
2 Correct 1 ms 432 KB Guessed the password with 105 queries.
3 Correct 0 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 13 ms 1204 KB Guessed the password with 2751 queries.
8 Correct 20 ms 720 KB Guessed the password with 5071 queries.
9 Correct 20 ms 720 KB Guessed the password with 4586 queries.
10 Correct 41 ms 716 KB Guessed the password with 8085 queries.
11 Correct 40 ms 1488 KB Guessed the password with 8159 queries.
12 Correct 34 ms 1004 KB Guessed the password with 8159 queries.
13 Correct 51 ms 740 KB Guessed the password with 11503 queries.
14 Correct 48 ms 968 KB Guessed the password with 11603 queries.
15 Correct 42 ms 1472 KB Guessed the password with 10883 queries.
16 Correct 47 ms 960 KB Guessed the password with 10858 queries.
17 Correct 46 ms 996 KB Guessed the password with 10210 queries.
18 Correct 42 ms 988 KB Guessed the password with 10243 queries.
19 Correct 51 ms 968 KB Guessed the password with 9684 queries.
20 Correct 48 ms 984 KB Guessed the password with 9779 queries.
21 Correct 55 ms 740 KB Guessed the password with 11640 queries.
22 Correct 51 ms 1200 KB Guessed the password with 11707 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 56 queries.
2 Correct 1 ms 432 KB Guessed the password with 105 queries.
3 Correct 0 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 13 ms 1204 KB Guessed the password with 2751 queries.
8 Correct 20 ms 720 KB Guessed the password with 5071 queries.
9 Correct 20 ms 720 KB Guessed the password with 4586 queries.
10 Correct 41 ms 716 KB Guessed the password with 8085 queries.
11 Correct 40 ms 1488 KB Guessed the password with 8159 queries.
12 Correct 34 ms 1004 KB Guessed the password with 8159 queries.
13 Correct 51 ms 740 KB Guessed the password with 11503 queries.
14 Correct 48 ms 968 KB Guessed the password with 11603 queries.
15 Correct 42 ms 1472 KB Guessed the password with 10883 queries.
16 Correct 47 ms 960 KB Guessed the password with 10858 queries.
17 Correct 46 ms 996 KB Guessed the password with 10210 queries.
18 Correct 42 ms 988 KB Guessed the password with 10243 queries.
19 Correct 51 ms 968 KB Guessed the password with 9684 queries.
20 Correct 48 ms 984 KB Guessed the password with 9779 queries.
21 Correct 55 ms 740 KB Guessed the password with 11640 queries.
22 Correct 51 ms 1200 KB Guessed the password with 11707 queries.
23 Correct 111 ms 1516 KB Guessed the password with 23648 queries.
24 Correct 95 ms 1264 KB Guessed the password with 20966 queries.
25 Correct 109 ms 1720 KB Guessed the password with 23670 queries.
26 Correct 87 ms 1616 KB Guessed the password with 19098 queries.
27 Correct 108 ms 1552 KB Guessed the password with 23698 queries.
28 Correct 97 ms 1252 KB Guessed the password with 16823 queries.
29 Correct 110 ms 1400 KB Guessed the password with 23708 queries.
30 Correct 70 ms 1484 KB Guessed the password with 14393 queries.