oj.uz

Submission #848819

# Submission time Handle Problem Language Result Execution time Memory
848819 2023-09-13T14:22:19 Z TahirAliyev Password (RMI18_password) C++17
50 / 100
 263 ms 1220 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++;
    }
    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());
    }
    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:33: 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()){
      |            ~~~~~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 87 queries.
2 Correct 1 ms 432 KB Guessed the password with 154 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 93 queries.
3 Correct 1 ms 344 KB Guessed the password with 103 queries.
4 Correct 1 ms 344 KB Guessed the password with 204 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 956 KB Guessed the password with 6382 queries.
2 Correct 45 ms 956 KB Guessed the password with 9057 queries.
3 Correct 55 ms 952 KB Guessed the password with 12571 queries.
4 Correct 87 ms 732 KB Guessed the password with 19055 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 87 queries.
2 Correct 1 ms 432 KB Guessed the password with 154 queries.
3 Correct 1 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 103 queries.
6 Correct 1 ms 344 KB Guessed the password with 204 queries.
7 Correct 28 ms 956 KB Guessed the password with 6382 queries.
8 Correct 45 ms 956 KB Guessed the password with 9057 queries.
9 Correct 55 ms 952 KB Guessed the password with 12571 queries.
10 Correct 87 ms 732 KB Guessed the password with 19055 queries.
11 Correct 55 ms 1208 KB Guessed the password with 11488 queries.
12 Correct 197 ms 964 KB Guessed the password with 39142 queries.
13 Correct 111 ms 1212 KB Guessed the password with 22363 queries.
14 Correct 245 ms 1220 KB Guessed the password with 49257 queries.
15 Correct 117 ms 956 KB Guessed the password with 22043 queries.
16 Correct 232 ms 712 KB Guessed the password with 46022 queries.
17 Correct 69 ms 716 KB Guessed the password with 12698 queries.
18 Incorrect 263 ms 700 KB Could not guess the password with 50000 queries.
19 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 87 queries.
2 Correct 1 ms 432 KB Guessed the password with 154 queries.
3 Correct 1 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 103 queries.
6 Correct 1 ms 344 KB Guessed the password with 204 queries.
7 Correct 28 ms 956 KB Guessed the password with 6382 queries.
8 Correct 45 ms 956 KB Guessed the password with 9057 queries.
9 Correct 55 ms 952 KB Guessed the password with 12571 queries.
10 Correct 87 ms 732 KB Guessed the password with 19055 queries.
11 Correct 55 ms 1208 KB Guessed the password with 11488 queries.
12 Correct 197 ms 964 KB Guessed the password with 39142 queries.
13 Correct 111 ms 1212 KB Guessed the password with 22363 queries.
14 Correct 245 ms 1220 KB Guessed the password with 49257 queries.
15 Correct 117 ms 956 KB Guessed the password with 22043 queries.
16 Correct 232 ms 712 KB Guessed the password with 46022 queries.
17 Correct 69 ms 716 KB Guessed the password with 12698 queries.
18 Incorrect 263 ms 700 KB Could not guess the password with 50000 queries.
19 Halted 0 ms 0 KB -