oj.uz

Submission #709394

# Submission time Handle Problem Language Result Execution time Memory
709394 2023-03-13T13:56:10 Z beepbeepsheep Password (RMI18_password) C++17
50 / 100
 283 ms 348 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 87 queries.
2 Correct 2 ms 208 KB Guessed the password with 154 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 2 ms 208 KB Guessed the password with 129 queries.
3 Correct 1 ms 208 KB Guessed the password with 169 queries.
4 Correct 3 ms 304 KB Guessed the password with 264 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 324 KB Guessed the password with 8258 queries.
2 Correct 97 ms 336 KB Guessed the password with 10637 queries.
3 Correct 221 ms 332 KB Guessed the password with 19402 queries.
4 Correct 198 ms 348 KB Guessed the password with 26458 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 87 queries.
2 Correct 2 ms 208 KB Guessed the password with 154 queries.
3 Correct 1 ms 208 KB Guessed the password with 48 queries.
4 Correct 2 ms 208 KB Guessed the password with 129 queries.
5 Correct 1 ms 208 KB Guessed the password with 169 queries.
6 Correct 3 ms 304 KB Guessed the password with 264 queries.
7 Correct 62 ms 324 KB Guessed the password with 8258 queries.
8 Correct 97 ms 336 KB Guessed the password with 10637 queries.
9 Correct 221 ms 332 KB Guessed the password with 19402 queries.
10 Correct 198 ms 348 KB Guessed the password with 26458 queries.
11 Incorrect 283 ms 344 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 87 queries.
2 Correct 2 ms 208 KB Guessed the password with 154 queries.
3 Correct 1 ms 208 KB Guessed the password with 48 queries.
4 Correct 2 ms 208 KB Guessed the password with 129 queries.
5 Correct 1 ms 208 KB Guessed the password with 169 queries.
6 Correct 3 ms 304 KB Guessed the password with 264 queries.
7 Correct 62 ms 324 KB Guessed the password with 8258 queries.
8 Correct 97 ms 336 KB Guessed the password with 10637 queries.
9 Correct 221 ms 332 KB Guessed the password with 19402 queries.
10 Correct 198 ms 348 KB Guessed the password with 26458 queries.
11 Incorrect 283 ms 344 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -