oj.uz

Submission #773332

# Submission time Handle Problem Language Result Execution time Memory
773332 2023-07-04T22:28:57 Z Khizri Password (RMI18_password) C++17
50 / 100
 375 ms 556 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
using namespace std;
int query(string q);
int mxn=2e5+5;
int k;
string mrg(string a,string b){
    string x;
    int idx=0;
    for(int i=0;i<b.size();i++){
        for(int j=idx;j<=a.size();j++){
            x=a;
            x.insert(x.begin()+j,b[i]);
            if(query(x)==x.size()){
                a=x;
                idx=j;
                break;
            }
        }
    }
    return a;
}
string guess(int n, int kx){
    char cc='a';
    int k=kx;
    kx--;
    while(kx--){
        cc++;
    }
    priority_queue<string,vector<string>,greater<string>>q;
    for(char c='a';c<=cc;c++){
        string s="";
        for(int j=1;j<=n;j++){
            s+=c;
        }
        int x=query(s);
        s="";
        for(int i=1;i<=x;i++){
            s+=c;
        }
        if(s.size()>0){
            q.push(s);
        }
    }
    while(q.size()>1){
        string a=q.top();
        q.pop();
        string b=q.top();
        q.pop();
        string x=mrg(a,b);
        q.push(x);
    }
    return q.top();
}

Compilation message

password.cpp: In function 'std::string mrg(std::string, std::string)':
password.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0;i<b.size();i++){
      |                 ~^~~~~~~~~
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 |         for(int j=idx;j<=a.size();j++){
      |                       ~^~~~~~~~~~
password.cpp:24:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |             if(query(x)==x.size()){
      |                ~~~~~~~~^~~~~~~~~~
password.cpp: In function 'std::string guess(int, int)':
password.cpp:35:9: warning: unused variable 'k' [-Wunused-variable]
   35 |     int k=kx;
      |         ^

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 73 queries.
2 Correct 2 ms 208 KB Guessed the password with 135 queries.
3 Correct 1 ms 208 KB Guessed the password with 93 queries.
4 Correct 3 ms 208 KB Guessed the password with 306 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 428 KB Guessed the password with 5492 queries.
2 Correct 92 ms 328 KB Guessed the password with 11382 queries.
3 Correct 121 ms 332 KB Guessed the password with 14049 queries.
4 Correct 105 ms 556 KB Guessed the password with 22311 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 76 queries.
2 Correct 2 ms 208 KB Guessed the password with 187 queries.
3 Correct 1 ms 208 KB Guessed the password with 73 queries.
4 Correct 2 ms 208 KB Guessed the password with 135 queries.
5 Correct 1 ms 208 KB Guessed the password with 93 queries.
6 Correct 3 ms 208 KB Guessed the password with 306 queries.
7 Correct 49 ms 428 KB Guessed the password with 5492 queries.
8 Correct 92 ms 328 KB Guessed the password with 11382 queries.
9 Correct 121 ms 332 KB Guessed the password with 14049 queries.
10 Correct 105 ms 556 KB Guessed the password with 22311 queries.
11 Incorrect 375 ms 332 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 76 queries.
2 Correct 2 ms 208 KB Guessed the password with 187 queries.
3 Correct 1 ms 208 KB Guessed the password with 73 queries.
4 Correct 2 ms 208 KB Guessed the password with 135 queries.
5 Correct 1 ms 208 KB Guessed the password with 93 queries.
6 Correct 3 ms 208 KB Guessed the password with 306 queries.
7 Correct 49 ms 428 KB Guessed the password with 5492 queries.
8 Correct 92 ms 328 KB Guessed the password with 11382 queries.
9 Correct 121 ms 332 KB Guessed the password with 14049 queries.
10 Correct 105 ms 556 KB Guessed the password with 22311 queries.
11 Incorrect 375 ms 332 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -