oj.uz

Submission #848813

# Submission time Handle Problem Language Result Execution time Memory
848813 2023-09-13T14:12:25 Z TahirAliyev Password (RMI18_password) C++17
50 / 100
 272 ms 1216 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);
        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: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 86 queries.
2 Correct 1 ms 436 KB Guessed the password with 150 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 92 queries.
4 Correct 1 ms 344 KB Guessed the password with 201 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 716 KB Guessed the password with 6379 queries.
2 Correct 38 ms 940 KB Guessed the password with 9049 queries.
3 Correct 59 ms 464 KB Guessed the password with 12565 queries.
4 Correct 100 ms 964 KB Guessed the password with 19047 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 86 queries.
2 Correct 1 ms 436 KB Guessed the password with 150 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 92 queries.
6 Correct 1 ms 344 KB Guessed the password with 201 queries.
7 Correct 28 ms 716 KB Guessed the password with 6379 queries.
8 Correct 38 ms 940 KB Guessed the password with 9049 queries.
9 Correct 59 ms 464 KB Guessed the password with 12565 queries.
10 Correct 100 ms 964 KB Guessed the password with 19047 queries.
11 Correct 57 ms 716 KB Guessed the password with 11486 queries.
12 Correct 209 ms 704 KB Guessed the password with 39139 queries.
13 Correct 112 ms 988 KB Guessed the password with 22355 queries.
14 Correct 251 ms 728 KB Guessed the password with 49255 queries.
15 Correct 111 ms 972 KB Guessed the password with 22041 queries.
16 Correct 234 ms 1204 KB Guessed the password with 46016 queries.
17 Correct 62 ms 744 KB Guessed the password with 12677 queries.
18 Incorrect 272 ms 1216 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 86 queries.
2 Correct 1 ms 436 KB Guessed the password with 150 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 92 queries.
6 Correct 1 ms 344 KB Guessed the password with 201 queries.
7 Correct 28 ms 716 KB Guessed the password with 6379 queries.
8 Correct 38 ms 940 KB Guessed the password with 9049 queries.
9 Correct 59 ms 464 KB Guessed the password with 12565 queries.
10 Correct 100 ms 964 KB Guessed the password with 19047 queries.
11 Correct 57 ms 716 KB Guessed the password with 11486 queries.
12 Correct 209 ms 704 KB Guessed the password with 39139 queries.
13 Correct 112 ms 988 KB Guessed the password with 22355 queries.
14 Correct 251 ms 728 KB Guessed the password with 49255 queries.
15 Correct 111 ms 972 KB Guessed the password with 22041 queries.
16 Correct 234 ms 1204 KB Guessed the password with 46016 queries.
17 Correct 62 ms 744 KB Guessed the password with 12677 queries.
18 Incorrect 272 ms 1216 KB Could not guess the password with 50000 queries.
19 Halted 0 ms 0 KB -