oj.uz

Submission #773333

# Submission time Handle Problem Language Result Execution time Memory
773333 2023-07-04T22:30:14 Z Khizri Password (RMI18_password) C++17
50 / 100
 340 ms 448 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+1;
                break;
            }
        }
    }
    //cout<<a<<endl;
    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="";
        //cout<<x<<endl;
        for(int i=1;i<=x;i++){
            s+=c;
        }
        //cout<<s<<endl;
        if(s.size()>0){
            q.push(s);
        }
        //c++;
    }
    while(q.size()>1){
        string a=q.top();
        q.pop();
        string b=q.top();
        q.pop();
        string x=mrg(a,b);
        //cout<<x<<endl;
        q.push(x);
    }
    return q.top();
}
//10 26 adfsfgsdfz

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:36:9: warning: unused variable 'k' [-Wunused-variable]
   36 |     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 0 ms 208 KB Guessed the password with 48 queries.
2 Correct 1 ms 208 KB Guessed the password with 116 queries.
3 Correct 2 ms 256 KB Guessed the password with 93 queries.
4 Correct 3 ms 208 KB Guessed the password with 221 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 320 KB Guessed the password with 4580 queries.
2 Correct 83 ms 312 KB Guessed the password with 10213 queries.
3 Correct 108 ms 324 KB Guessed the password with 12520 queries.
4 Correct 126 ms 340 KB Guessed the password with 20417 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 0 ms 208 KB Guessed the password with 48 queries.
4 Correct 1 ms 208 KB Guessed the password with 116 queries.
5 Correct 2 ms 256 KB Guessed the password with 93 queries.
6 Correct 3 ms 208 KB Guessed the password with 221 queries.
7 Correct 40 ms 320 KB Guessed the password with 4580 queries.
8 Correct 83 ms 312 KB Guessed the password with 10213 queries.
9 Correct 108 ms 324 KB Guessed the password with 12520 queries.
10 Correct 126 ms 340 KB Guessed the password with 20417 queries.
11 Correct 243 ms 328 KB Guessed the password with 49512 queries.
12 Correct 77 ms 436 KB Guessed the password with 11399 queries.
13 Correct 246 ms 348 KB Guessed the password with 47683 queries.
14 Correct 168 ms 352 KB Guessed the password with 21361 queries.
15 Correct 340 ms 332 KB Guessed the password with 44836 queries.
16 Correct 122 ms 376 KB Guessed the password with 17948 queries.
17 Correct 296 ms 448 KB Guessed the password with 49794 queries.
18 Correct 63 ms 348 KB Guessed the password with 14856 queries.
19 Incorrect 325 ms 320 KB Could not guess the password with 50000 queries.
20 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 0 ms 208 KB Guessed the password with 48 queries.
4 Correct 1 ms 208 KB Guessed the password with 116 queries.
5 Correct 2 ms 256 KB Guessed the password with 93 queries.
6 Correct 3 ms 208 KB Guessed the password with 221 queries.
7 Correct 40 ms 320 KB Guessed the password with 4580 queries.
8 Correct 83 ms 312 KB Guessed the password with 10213 queries.
9 Correct 108 ms 324 KB Guessed the password with 12520 queries.
10 Correct 126 ms 340 KB Guessed the password with 20417 queries.
11 Correct 243 ms 328 KB Guessed the password with 49512 queries.
12 Correct 77 ms 436 KB Guessed the password with 11399 queries.
13 Correct 246 ms 348 KB Guessed the password with 47683 queries.
14 Correct 168 ms 352 KB Guessed the password with 21361 queries.
15 Correct 340 ms 332 KB Guessed the password with 44836 queries.
16 Correct 122 ms 376 KB Guessed the password with 17948 queries.
17 Correct 296 ms 448 KB Guessed the password with 49794 queries.
18 Correct 63 ms 348 KB Guessed the password with 14856 queries.
19 Incorrect 325 ms 320 KB Could not guess the password with 50000 queries.
20 Halted 0 ms 0 KB -