oj.uz

Submission #773325

# Submission time Handle Problem Language Result Execution time Memory
773325 2023-07-04T21:47:13 Z TheSahib Password (RMI18_password) C++14
100 / 100
 209 ms 508 KB 
#include <bits/stdc++.h>
 
#define ll long long
#define pii pair<int, int>
 
using namespace std;
 
int query(string s);

string merge(string s1, string s2){
    int p = 0;
    string ans = s1;
    string z = "";
    for (int i = 0; i <= ans.size() && p < s2.size(); i++)
    {
        z = ans;
        z.insert(z.begin() + i, s2[p]);
        int b = query(z);
        if(b == z.size()){
            ans = z;
            p++;
        }
    }
    return ans;
}

bool comp(string& a, string& b){
    return a.size() > b.size();
}
 
string guess(int n, int s){
    vector<string> ss;
    for (int c = 'a'; c < 'a' + s; c++)
    {
        string a;
        for (int i = 0; i < n; i++)
        {
            a += c;
        }
        int b = query(a);
        a.erase(a.begin() + b, a.end());
        if(a.empty()) continue;
        ss.push_back(a);
    }
    while(ss.size() != 1){
        sort(ss.begin(), ss.end(), comp);
        string a = merge(ss[ss.size() - 1], ss[ss.size() - 2]);
        ss.pop_back();
        ss.pop_back();
        ss.push_back(a);
    }
    
    return ss[0];
}

Compilation message

password.cpp: In function 'std::string merge(std::string, std::string)':
password.cpp:14:23: 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 = 0; i <= ans.size() && p < s2.size(); i++)
      |                     ~~^~~~~~~~~~~~~
password.cpp:14:42: 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 = 0; i <= ans.size() && p < s2.size(); i++)
      |                                        ~~^~~~~~~~~~~
password.cpp:19:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         if(b == z.size()){
      |            ~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 63 queries.
2 Correct 2 ms 208 KB Guessed the password with 125 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 48 queries.
2 Correct 1 ms 208 KB Guessed the password with 93 queries.
3 Correct 1 ms 208 KB Guessed the password with 91 queries.
4 Correct 1 ms 208 KB Guessed the password with 180 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 308 KB Guessed the password with 2760 queries.
2 Correct 40 ms 320 KB Guessed the password with 5104 queries.
3 Correct 26 ms 332 KB Guessed the password with 4601 queries.
4 Correct 68 ms 440 KB Guessed the password with 8101 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 63 queries.
2 Correct 2 ms 208 KB Guessed the password with 125 queries.
3 Correct 1 ms 208 KB Guessed the password with 48 queries.
4 Correct 1 ms 208 KB Guessed the password with 93 queries.
5 Correct 1 ms 208 KB Guessed the password with 91 queries.
6 Correct 1 ms 208 KB Guessed the password with 180 queries.
7 Correct 17 ms 308 KB Guessed the password with 2760 queries.
8 Correct 40 ms 320 KB Guessed the password with 5104 queries.
9 Correct 26 ms 332 KB Guessed the password with 4601 queries.
10 Correct 68 ms 440 KB Guessed the password with 8101 queries.
11 Correct 76 ms 352 KB Guessed the password with 8180 queries.
12 Correct 69 ms 448 KB Guessed the password with 8186 queries.
13 Correct 85 ms 372 KB Guessed the password with 11548 queries.
14 Correct 92 ms 476 KB Guessed the password with 11678 queries.
15 Correct 75 ms 352 KB Guessed the password with 10908 queries.
16 Correct 84 ms 368 KB Guessed the password with 10877 queries.
17 Correct 53 ms 432 KB Guessed the password with 10241 queries.
18 Correct 71 ms 348 KB Guessed the password with 10275 queries.
19 Correct 79 ms 348 KB Guessed the password with 9709 queries.
20 Correct 55 ms 344 KB Guessed the password with 9797 queries.
21 Correct 109 ms 348 KB Guessed the password with 11739 queries.
22 Correct 101 ms 352 KB Guessed the password with 11780 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 63 queries.
2 Correct 2 ms 208 KB Guessed the password with 125 queries.
3 Correct 1 ms 208 KB Guessed the password with 48 queries.
4 Correct 1 ms 208 KB Guessed the password with 93 queries.
5 Correct 1 ms 208 KB Guessed the password with 91 queries.
6 Correct 1 ms 208 KB Guessed the password with 180 queries.
7 Correct 17 ms 308 KB Guessed the password with 2760 queries.
8 Correct 40 ms 320 KB Guessed the password with 5104 queries.
9 Correct 26 ms 332 KB Guessed the password with 4601 queries.
10 Correct 68 ms 440 KB Guessed the password with 8101 queries.
11 Correct 76 ms 352 KB Guessed the password with 8180 queries.
12 Correct 69 ms 448 KB Guessed the password with 8186 queries.
13 Correct 85 ms 372 KB Guessed the password with 11548 queries.
14 Correct 92 ms 476 KB Guessed the password with 11678 queries.
15 Correct 75 ms 352 KB Guessed the password with 10908 queries.
16 Correct 84 ms 368 KB Guessed the password with 10877 queries.
17 Correct 53 ms 432 KB Guessed the password with 10241 queries.
18 Correct 71 ms 348 KB Guessed the password with 10275 queries.
19 Correct 79 ms 348 KB Guessed the password with 9709 queries.
20 Correct 55 ms 344 KB Guessed the password with 9797 queries.
21 Correct 109 ms 348 KB Guessed the password with 11739 queries.
22 Correct 101 ms 352 KB Guessed the password with 11780 queries.
23 Correct 171 ms 392 KB Guessed the password with 23758 queries.
24 Correct 181 ms 508 KB Guessed the password with 21005 queries.
25 Correct 209 ms 464 KB Guessed the password with 23742 queries.
26 Correct 129 ms 388 KB Guessed the password with 19120 queries.
27 Correct 150 ms 492 KB Guessed the password with 23715 queries.
28 Correct 117 ms 384 KB Guessed the password with 16857 queries.
29 Correct 155 ms 384 KB Guessed the password with 23732 queries.
30 Correct 130 ms 392 KB Guessed the password with 14420 queries.