oj.uz

Submission #773334

# Submission time Handle Problem Language Result Execution time Memory
773334 2023-07-04T22:38:47 Z Khizri Password (RMI18_password) C++17
50 / 100
 406 ms 344 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;
}
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<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: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 132 queries.
2 Correct 3 ms 296 KB Guessed the password with 295 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 127 queries.
3 Correct 2 ms 208 KB Guessed the password with 103 queries.
4 Correct 3 ms 208 KB Guessed the password with 218 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 312 KB Guessed the password with 4747 queries.
2 Correct 68 ms 324 KB Guessed the password with 10660 queries.
3 Correct 61 ms 308 KB Guessed the password with 14327 queries.
4 Correct 144 ms 304 KB Guessed the password with 20804 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 132 queries.
2 Correct 3 ms 296 KB Guessed the password with 295 queries.
3 Correct 1 ms 208 KB Guessed the password with 52 queries.
4 Correct 1 ms 208 KB Guessed the password with 127 queries.
5 Correct 2 ms 208 KB Guessed the password with 103 queries.
6 Correct 3 ms 208 KB Guessed the password with 218 queries.
7 Correct 41 ms 312 KB Guessed the password with 4747 queries.
8 Correct 68 ms 324 KB Guessed the password with 10660 queries.
9 Correct 61 ms 308 KB Guessed the password with 14327 queries.
10 Correct 144 ms 304 KB Guessed the password with 20804 queries.
11 Incorrect 406 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 132 queries.
2 Correct 3 ms 296 KB Guessed the password with 295 queries.
3 Correct 1 ms 208 KB Guessed the password with 52 queries.
4 Correct 1 ms 208 KB Guessed the password with 127 queries.
5 Correct 2 ms 208 KB Guessed the password with 103 queries.
6 Correct 3 ms 208 KB Guessed the password with 218 queries.
7 Correct 41 ms 312 KB Guessed the password with 4747 queries.
8 Correct 68 ms 324 KB Guessed the password with 10660 queries.
9 Correct 61 ms 308 KB Guessed the password with 14327 queries.
10 Correct 144 ms 304 KB Guessed the password with 20804 queries.
11 Incorrect 406 ms 344 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -