oj.uz

Submission #848803

# Submission time Handle Problem Language Result Execution time Memory
848803 2023-09-13T14:02:20 Z TahirAliyev Password (RMI18_password) C++17
50 / 100
 277 ms 1200 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++;
        }
        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: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 436 KB Guessed the password with 155 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 500 KB Guessed the password with 146 queries.
3 Correct 1 ms 344 KB Guessed the password with 113 queries.
4 Correct 1 ms 344 KB Guessed the password with 281 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 700 KB Guessed the password with 7203 queries.
2 Correct 48 ms 968 KB Guessed the password with 10317 queries.
3 Correct 63 ms 720 KB Guessed the password with 14101 queries.
4 Correct 91 ms 988 KB Guessed the password with 20875 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 436 KB Guessed the password with 155 queries.
3 Correct 1 ms 344 KB Guessed the password with 73 queries.
4 Correct 1 ms 500 KB Guessed the password with 146 queries.
5 Correct 1 ms 344 KB Guessed the password with 113 queries.
6 Correct 1 ms 344 KB Guessed the password with 281 queries.
7 Correct 33 ms 700 KB Guessed the password with 7203 queries.
8 Correct 48 ms 968 KB Guessed the password with 10317 queries.
9 Correct 63 ms 720 KB Guessed the password with 14101 queries.
10 Correct 91 ms 988 KB Guessed the password with 20875 queries.
11 Correct 64 ms 1200 KB Guessed the password with 14169 queries.
12 Correct 238 ms 948 KB Guessed the password with 41276 queries.
13 Correct 120 ms 964 KB Guessed the password with 25281 queries.
14 Incorrect 277 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 87 queries.
2 Correct 1 ms 436 KB Guessed the password with 155 queries.
3 Correct 1 ms 344 KB Guessed the password with 73 queries.
4 Correct 1 ms 500 KB Guessed the password with 146 queries.
5 Correct 1 ms 344 KB Guessed the password with 113 queries.
6 Correct 1 ms 344 KB Guessed the password with 281 queries.
7 Correct 33 ms 700 KB Guessed the password with 7203 queries.
8 Correct 48 ms 968 KB Guessed the password with 10317 queries.
9 Correct 63 ms 720 KB Guessed the password with 14101 queries.
10 Correct 91 ms 988 KB Guessed the password with 20875 queries.
11 Correct 64 ms 1200 KB Guessed the password with 14169 queries.
12 Correct 238 ms 948 KB Guessed the password with 41276 queries.
13 Correct 120 ms 964 KB Guessed the password with 25281 queries.
14 Incorrect 277 ms 728 KB Could not guess the password with 50000 queries.
15 Halted 0 ms 0 KB -