oj.uz

Submission #709396

# Submission time Handle Problem Language Result Execution time Memory
709396 2023-03-13T13:57:03 Z beepbeepsheep Password (RMI18_password) C++17
100 / 100
 252 ms 752 KB 
#include <bits/stdc++.h>
using namespace std;
int arr[26];
int query(string s);
string build(string &s, char c, int pos){
    string ret="";
    for (int i=0;i<pos;i++){
        ret+=s[i];
    }
    ret+=c;
    for (int i=pos;i<s.size();i++){
        ret+=s[i];
    }
    return ret;
}
string mrg(string a, string b){
    int lptr=0,rptr=0;
    string ans="";
    while (lptr<a.size() && rptr<b.size()){
        string test=ans+a[lptr]+b.substr(rptr);
        if (query(test)==test.length()){
            ans+=a[lptr];
            lptr++;
        } else{
            ans+=b[rptr];
            rptr++;
        }
    }
    while (lptr<a.size()){
        ans+=a[lptr];
        lptr++;
    }
    while (rptr<b.size()){
        ans+=b[rptr];
        rptr++;
    }
    return ans;
}
string dup(char c, int n){
    string ret="";
    for (int i=0;i<n;i++) ret+=c;
    return ret;
}
priority_queue<pair<int,string>> pq;
string guess(int n, int s){
    for (int i=0;i<s;i++){
        arr[i]=query(dup(i+'a',n));
        if (arr[i]==0) continue;
        pq.emplace(-arr[i],dup(i+'a',arr[i]));
    }
    while (pq.size()>1){
        string a=pq.top().second;
        pq.pop();
        string b=pq.top().second;
        pq.pop();
        string ans=mrg(a,b);
        pq.emplace(-ans.length(),ans);
    }
    return pq.top().second;
}

Compilation message

password.cpp: In function 'std::string build(std::string&, char, int)':
password.cpp:11:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for (int i=pos;i<s.size();i++){
      |                    ~^~~~~~~~~
password.cpp: In function 'std::string mrg(std::string, std::string)':
password.cpp:19:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     while (lptr<a.size() && rptr<b.size()){
      |            ~~~~^~~~~~~~~
password.cpp:19:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     while (lptr<a.size() && rptr<b.size()){
      |                             ~~~~^~~~~~~~~
password.cpp:21:24: 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(test)==test.length()){
      |             ~~~~~~~~~~~^~~~~~~~~~~~~~~
password.cpp:29:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     while (lptr<a.size()){
      |            ~~~~^~~~~~~~~
password.cpp:33:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     while (rptr<b.size()){
      |            ~~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 49 queries.
2 Correct 1 ms 208 KB Guessed the password with 90 queries.
3 Correct 1 ms 208 KB Guessed the password with 92 queries.
4 Correct 1 ms 208 KB Guessed the password with 178 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 316 KB Guessed the password with 2750 queries.
2 Correct 34 ms 304 KB Guessed the password with 5070 queries.
3 Correct 46 ms 564 KB Guessed the password with 4586 queries.
4 Correct 68 ms 468 KB Guessed the password with 8085 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 57 queries.
2 Correct 2 ms 208 KB Guessed the password with 103 queries.
3 Correct 1 ms 208 KB Guessed the password with 49 queries.
4 Correct 1 ms 208 KB Guessed the password with 90 queries.
5 Correct 1 ms 208 KB Guessed the password with 92 queries.
6 Correct 1 ms 208 KB Guessed the password with 178 queries.
7 Correct 25 ms 316 KB Guessed the password with 2750 queries.
8 Correct 34 ms 304 KB Guessed the password with 5070 queries.
9 Correct 46 ms 564 KB Guessed the password with 4586 queries.
10 Correct 68 ms 468 KB Guessed the password with 8085 queries.
11 Correct 99 ms 356 KB Guessed the password with 8154 queries.
12 Correct 74 ms 308 KB Guessed the password with 8162 queries.
13 Correct 136 ms 380 KB Guessed the password with 11500 queries.
14 Correct 115 ms 368 KB Guessed the password with 11602 queries.
15 Correct 140 ms 376 KB Guessed the password with 10878 queries.
16 Correct 130 ms 380 KB Guessed the password with 10862 queries.
17 Correct 104 ms 368 KB Guessed the password with 10209 queries.
18 Correct 129 ms 364 KB Guessed the password with 10245 queries.
19 Correct 88 ms 356 KB Guessed the password with 9687 queries.
20 Correct 110 ms 352 KB Guessed the password with 9778 queries.
21 Correct 117 ms 312 KB Guessed the password with 11641 queries.
22 Correct 145 ms 312 KB Guessed the password with 11708 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 57 queries.
2 Correct 2 ms 208 KB Guessed the password with 103 queries.
3 Correct 1 ms 208 KB Guessed the password with 49 queries.
4 Correct 1 ms 208 KB Guessed the password with 90 queries.
5 Correct 1 ms 208 KB Guessed the password with 92 queries.
6 Correct 1 ms 208 KB Guessed the password with 178 queries.
7 Correct 25 ms 316 KB Guessed the password with 2750 queries.
8 Correct 34 ms 304 KB Guessed the password with 5070 queries.
9 Correct 46 ms 564 KB Guessed the password with 4586 queries.
10 Correct 68 ms 468 KB Guessed the password with 8085 queries.
11 Correct 99 ms 356 KB Guessed the password with 8154 queries.
12 Correct 74 ms 308 KB Guessed the password with 8162 queries.
13 Correct 136 ms 380 KB Guessed the password with 11500 queries.
14 Correct 115 ms 368 KB Guessed the password with 11602 queries.
15 Correct 140 ms 376 KB Guessed the password with 10878 queries.
16 Correct 130 ms 380 KB Guessed the password with 10862 queries.
17 Correct 104 ms 368 KB Guessed the password with 10209 queries.
18 Correct 129 ms 364 KB Guessed the password with 10245 queries.
19 Correct 88 ms 356 KB Guessed the password with 9687 queries.
20 Correct 110 ms 352 KB Guessed the password with 9778 queries.
21 Correct 117 ms 312 KB Guessed the password with 11641 queries.
22 Correct 145 ms 312 KB Guessed the password with 11708 queries.
23 Correct 234 ms 404 KB Guessed the password with 23635 queries.
24 Correct 222 ms 620 KB Guessed the password with 20965 queries.
25 Correct 229 ms 612 KB Guessed the password with 23669 queries.
26 Correct 185 ms 520 KB Guessed the password with 19099 queries.
27 Correct 234 ms 520 KB Guessed the password with 23720 queries.
28 Correct 183 ms 496 KB Guessed the password with 16821 queries.
29 Correct 252 ms 752 KB Guessed the password with 23713 queries.
30 Correct 137 ms 480 KB Guessed the password with 14390 queries.