oj.uz

Submission #848805

# Submission time Handle Problem Language Result Execution time Memory
848805 2023-09-13T14:04:21 Z TahirAliyev Password (RMI18_password) C++17
50 / 100
 299 ms 1228 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()){
        if(p1 == s1.size()){
            for(int i = p2; i < s2.size(); i++){
                s1 += s2[i];
            }
            break;
        }
        q = s1;
        q.insert(q.begin() + p1, s2[p2]);
        if(query(q) == q.size()){
            s1 = q;
            p2++;
        }
        else{
            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);
        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:13:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |         if(p1 == s1.size()){
      |            ~~~^~~~~~~~~~~~
password.cpp:14:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |             for(int i = p2; i < s2.size(); i++){
      |                             ~~^~~~~~~~~~~
password.cpp:21:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         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 86 queries.
2 Correct 1 ms 440 KB Guessed the password with 151 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 73 queries.
2 Correct 1 ms 344 KB Guessed the password with 144 queries.
3 Correct 1 ms 344 KB Guessed the password with 92 queries.
4 Correct 1 ms 344 KB Guessed the password with 278 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1212 KB Guessed the password with 7200 queries.
2 Correct 53 ms 1228 KB Guessed the password with 10309 queries.
3 Correct 75 ms 960 KB Guessed the password with 14095 queries.
4 Correct 99 ms 1200 KB Guessed the password with 20867 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 440 KB Guessed the password with 151 queries.
3 Correct 1 ms 344 KB Guessed the password with 73 queries.
4 Correct 1 ms 344 KB Guessed the password with 144 queries.
5 Correct 1 ms 344 KB Guessed the password with 92 queries.
6 Correct 1 ms 344 KB Guessed the password with 278 queries.
7 Correct 32 ms 1212 KB Guessed the password with 7200 queries.
8 Correct 53 ms 1228 KB Guessed the password with 10309 queries.
9 Correct 75 ms 960 KB Guessed the password with 14095 queries.
10 Correct 99 ms 1200 KB Guessed the password with 20867 queries.
11 Correct 69 ms 732 KB Guessed the password with 14167 queries.
12 Correct 225 ms 964 KB Guessed the password with 41273 queries.
13 Correct 115 ms 940 KB Guessed the password with 25273 queries.
14 Incorrect 299 ms 728 KB Could not guess the password with 50000 queries.
15 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 440 KB Guessed the password with 151 queries.
3 Correct 1 ms 344 KB Guessed the password with 73 queries.
4 Correct 1 ms 344 KB Guessed the password with 144 queries.
5 Correct 1 ms 344 KB Guessed the password with 92 queries.
6 Correct 1 ms 344 KB Guessed the password with 278 queries.
7 Correct 32 ms 1212 KB Guessed the password with 7200 queries.
8 Correct 53 ms 1228 KB Guessed the password with 10309 queries.
9 Correct 75 ms 960 KB Guessed the password with 14095 queries.
10 Correct 99 ms 1200 KB Guessed the password with 20867 queries.
11 Correct 69 ms 732 KB Guessed the password with 14167 queries.
12 Correct 225 ms 964 KB Guessed the password with 41273 queries.
13 Correct 115 ms 940 KB Guessed the password with 25273 queries.
14 Incorrect 299 ms 728 KB Could not guess the password with 50000 queries.
15 Halted 0 ms 0 KB -