oj.uz

Submission #848817

# Submission time Handle Problem Language Result Execution time Memory
848817 2023-09-13T14:17:59 Z TahirAliyev Password (RMI18_password) C++17
50 / 100
 294 ms 1204 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;
        }
        if(a.empty()) continue;
        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 440 KB Guessed the password with 150 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 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 37 ms 952 KB Guessed the password with 6379 queries.
2 Correct 45 ms 1192 KB Guessed the password with 9049 queries.
3 Correct 63 ms 708 KB Guessed the password with 12565 queries.
4 Correct 86 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 440 KB Guessed the password with 150 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 92 queries.
6 Correct 1 ms 344 KB Guessed the password with 201 queries.
7 Correct 37 ms 952 KB Guessed the password with 6379 queries.
8 Correct 45 ms 1192 KB Guessed the password with 9049 queries.
9 Correct 63 ms 708 KB Guessed the password with 12565 queries.
10 Correct 86 ms 964 KB Guessed the password with 19047 queries.
11 Correct 57 ms 952 KB Guessed the password with 11486 queries.
12 Correct 234 ms 960 KB Guessed the password with 39139 queries.
13 Correct 108 ms 992 KB Guessed the password with 22355 queries.
14 Correct 294 ms 1200 KB Guessed the password with 49255 queries.
15 Correct 113 ms 1204 KB Guessed the password with 22041 queries.
16 Correct 236 ms 704 KB Guessed the password with 46016 queries.
17 Correct 62 ms 736 KB Guessed the password with 12677 queries.
18 Incorrect 239 ms 956 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 440 KB Guessed the password with 150 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 92 queries.
6 Correct 1 ms 344 KB Guessed the password with 201 queries.
7 Correct 37 ms 952 KB Guessed the password with 6379 queries.
8 Correct 45 ms 1192 KB Guessed the password with 9049 queries.
9 Correct 63 ms 708 KB Guessed the password with 12565 queries.
10 Correct 86 ms 964 KB Guessed the password with 19047 queries.
11 Correct 57 ms 952 KB Guessed the password with 11486 queries.
12 Correct 234 ms 960 KB Guessed the password with 39139 queries.
13 Correct 108 ms 992 KB Guessed the password with 22355 queries.
14 Correct 294 ms 1200 KB Guessed the password with 49255 queries.
15 Correct 113 ms 1204 KB Guessed the password with 22041 queries.
16 Correct 236 ms 704 KB Guessed the password with 46016 queries.
17 Correct 62 ms 736 KB Guessed the password with 12677 queries.
18 Incorrect 239 ms 956 KB Could not guess the password with 50000 queries.
19 Halted 0 ms 0 KB -