oj.uz

Submission #773337

# Submission time Handle Problem Language Result Execution time Memory
773337 2023-07-04T22:43:40 Z Khizri Password (RMI18_password) C++17
100 / 100
 196 ms 572 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<a.size();i++){
        for(int j=idx;j<=b.size();j++){
            x=b;
            x.insert(x.begin()+j,a[i]);
            if(query(x)==x.size()){
                b=x;
                idx=j+1;
                break;
            }
        }
    }
    //cout<<a<<endl;
    return b;
}
bool cmp(string a,string b){
    return a.size()<b.size();
}
string guess(int n, int kx){
    char cc='a';
    int k=kx;
    kx--;
    while(kx--){
        cc++;
    }
    vector<string>vt;
    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){
            vt.pb(s);
        }
        //c++;
    }
    sort(all(vt),cmp);
    while(vt.size()>1){
        string a=vt[0];
        string b=vt[1];
        string x=mrg(a,b);
        vt.erase(vt.begin());
        vt.erase(vt.begin());
        vt.pb(x);
        sort(all(vt),cmp);
        //cout<<x<<endl;
        //q.push(x);
    }
    return vt[0];
}
//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<a.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<=b.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:39:9: warning: unused variable 'k' [-Wunused-variable]
   39 |     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 69 queries.
2 Correct 1 ms 208 KB Guessed the password with 111 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 52 queries.
2 Correct 1 ms 208 KB Guessed the password with 92 queries.
3 Correct 1 ms 208 KB Guessed the password with 105 queries.
4 Correct 2 ms 208 KB Guessed the password with 179 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 312 KB Guessed the password with 2763 queries.
2 Correct 51 ms 300 KB Guessed the password with 5079 queries.
3 Correct 31 ms 308 KB Guessed the password with 4591 queries.
4 Correct 73 ms 336 KB Guessed the password with 8142 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 69 queries.
2 Correct 1 ms 208 KB Guessed the password with 111 queries.
3 Correct 1 ms 208 KB Guessed the password with 52 queries.
4 Correct 1 ms 208 KB Guessed the password with 92 queries.
5 Correct 1 ms 208 KB Guessed the password with 105 queries.
6 Correct 2 ms 208 KB Guessed the password with 179 queries.
7 Correct 21 ms 312 KB Guessed the password with 2763 queries.
8 Correct 51 ms 300 KB Guessed the password with 5079 queries.
9 Correct 31 ms 308 KB Guessed the password with 4591 queries.
10 Correct 73 ms 336 KB Guessed the password with 8142 queries.
11 Correct 61 ms 432 KB Guessed the password with 8171 queries.
12 Correct 79 ms 316 KB Guessed the password with 8177 queries.
13 Correct 62 ms 432 KB Guessed the password with 11524 queries.
14 Correct 102 ms 312 KB Guessed the password with 11621 queries.
15 Correct 70 ms 308 KB Guessed the password with 10899 queries.
16 Correct 94 ms 356 KB Guessed the password with 10881 queries.
17 Correct 79 ms 348 KB Guessed the password with 10228 queries.
18 Correct 78 ms 344 KB Guessed the password with 10288 queries.
19 Correct 87 ms 352 KB Guessed the password with 9706 queries.
20 Correct 65 ms 336 KB Guessed the password with 9801 queries.
21 Correct 98 ms 364 KB Guessed the password with 11691 queries.
22 Correct 78 ms 308 KB Guessed the password with 11774 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 69 queries.
2 Correct 1 ms 208 KB Guessed the password with 111 queries.
3 Correct 1 ms 208 KB Guessed the password with 52 queries.
4 Correct 1 ms 208 KB Guessed the password with 92 queries.
5 Correct 1 ms 208 KB Guessed the password with 105 queries.
6 Correct 2 ms 208 KB Guessed the password with 179 queries.
7 Correct 21 ms 312 KB Guessed the password with 2763 queries.
8 Correct 51 ms 300 KB Guessed the password with 5079 queries.
9 Correct 31 ms 308 KB Guessed the password with 4591 queries.
10 Correct 73 ms 336 KB Guessed the password with 8142 queries.
11 Correct 61 ms 432 KB Guessed the password with 8171 queries.
12 Correct 79 ms 316 KB Guessed the password with 8177 queries.
13 Correct 62 ms 432 KB Guessed the password with 11524 queries.
14 Correct 102 ms 312 KB Guessed the password with 11621 queries.
15 Correct 70 ms 308 KB Guessed the password with 10899 queries.
16 Correct 94 ms 356 KB Guessed the password with 10881 queries.
17 Correct 79 ms 348 KB Guessed the password with 10228 queries.
18 Correct 78 ms 344 KB Guessed the password with 10288 queries.
19 Correct 87 ms 352 KB Guessed the password with 9706 queries.
20 Correct 65 ms 336 KB Guessed the password with 9801 queries.
21 Correct 98 ms 364 KB Guessed the password with 11691 queries.
22 Correct 78 ms 308 KB Guessed the password with 11774 queries.
23 Correct 176 ms 392 KB Guessed the password with 23668 queries.
24 Correct 171 ms 572 KB Guessed the password with 20989 queries.
25 Correct 188 ms 540 KB Guessed the password with 23684 queries.
26 Correct 86 ms 472 KB Guessed the password with 19161 queries.
27 Correct 196 ms 484 KB Guessed the password with 23766 queries.
28 Correct 152 ms 500 KB Guessed the password with 16838 queries.
29 Correct 103 ms 384 KB Guessed the password with 23729 queries.
30 Correct 128 ms 400 KB Guessed the password with 14402 queries.