oj.uz

Submission #309034

# Submission time Handle Problem Language Result Execution time Memory
309034 2020-10-02T15:32:06 Z bigDuck Password (RMI18_password) C++14
100 / 100
 405 ms 588 KB 
#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount



int query(string str);
/*int query(string str){
cout<<str<<"\n"<<flush; int res; cin>>res; return res;
}*/







string guess(int n, int s){
stack<string> stv;
for(char c='a'; c<=('a'+s-1); c++){
    string st="";
    for(int i=0; i<n; i++){st.pb(c);}
    int ln=query(st);
    if(ln==0){continue;}
    if(ln>0){
        string s="";
        for(int i=0; i<ln; i++){
            s.pb(c);
        }
        stv.push(s);
    }
}


while(stv.size()>1){
    stack<string> stv2;
    while(stv.size()>1){
        string s1=stv.top(); stv.pop(); string s2=stv.top(); stv.pop();
        string s3="";
        int j=0, i=0;
        for(; i<s1.length() && j<s2.length(); i++){
            bool v=false;
            string s4=s3; s4.pb(s1[i]);
            for(int k=j; k<s2.length(); k++){
                s4.pb(s2[k]);
            }
            v=(query(s4)==(s4.length()));
            if(v){
                s3.pb(s1[i]);
            }
            else{
                s3.pb(s2[j]); j++; i--;
            }
        }

        while(i<s1.length()){
            s3.pb(s1[i]); i++;
        }
        while(j<s2.length()){
            s3.pb(s2[j]); j++;
        }
        stv2.push(s3);
    }

    while(!stv2.empty()){
        stv.push(stv2.top()); stv2.pop();
    }
}




return stv.top();
}


/*int main(){
cout<<guess(6, 26);




}*/

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:48:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(; i<s1.length() && j<s2.length(); i++){
      |               ~^~~~~~~~~~~~
password.cpp:48:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(; i<s1.length() && j<s2.length(); i++){
      |                                ~^~~~~~~~~~~~
password.cpp:51:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             for(int k=j; k<s2.length(); k++){
      |                          ~^~~~~~~~~~~~
password.cpp:54:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             v=(query(s4)==(s4.length()));
      |                ~~~~~~~~~^~~~~~~~~~~~~~~
password.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         while(i<s1.length()){
      |               ~^~~~~~~~~~~~
password.cpp:66:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         while(j<s2.length()){
      |               ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Guessed the password with 58 queries.
2 Correct 1 ms 256 KB Guessed the password with 103 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 48 queries.
2 Correct 1 ms 256 KB Guessed the password with 90 queries.
3 Correct 2 ms 256 KB Guessed the password with 170 queries.
4 Correct 3 ms 256 KB Guessed the password with 198 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 256 KB Guessed the password with 3824 queries.
2 Correct 53 ms 376 KB Guessed the password with 4971 queries.
3 Correct 79 ms 376 KB Guessed the password with 6557 queries.
4 Correct 124 ms 384 KB Guessed the password with 9000 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Guessed the password with 58 queries.
2 Correct 1 ms 256 KB Guessed the password with 103 queries.
3 Correct 1 ms 256 KB Guessed the password with 48 queries.
4 Correct 1 ms 256 KB Guessed the password with 90 queries.
5 Correct 2 ms 256 KB Guessed the password with 170 queries.
6 Correct 3 ms 256 KB Guessed the password with 198 queries.
7 Correct 46 ms 256 KB Guessed the password with 3824 queries.
8 Correct 53 ms 376 KB Guessed the password with 4971 queries.
9 Correct 79 ms 376 KB Guessed the password with 6557 queries.
10 Correct 124 ms 384 KB Guessed the password with 9000 queries.
11 Correct 166 ms 508 KB Guessed the password with 11299 queries.
12 Correct 186 ms 508 KB Guessed the password with 13424 queries.
13 Correct 223 ms 512 KB Guessed the password with 13414 queries.
14 Correct 178 ms 376 KB Guessed the password with 14652 queries.
15 Correct 166 ms 384 KB Guessed the password with 13401 queries.
16 Correct 227 ms 392 KB Guessed the password with 15312 queries.
17 Correct 238 ms 384 KB Guessed the password with 13666 queries.
18 Correct 195 ms 504 KB Guessed the password with 16182 queries.
19 Correct 234 ms 384 KB Guessed the password with 13552 queries.
20 Correct 187 ms 384 KB Guessed the password with 15702 queries.
21 Correct 237 ms 392 KB Guessed the password with 14882 queries.
22 Correct 202 ms 388 KB Guessed the password with 16691 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Guessed the password with 58 queries.
2 Correct 1 ms 256 KB Guessed the password with 103 queries.
3 Correct 1 ms 256 KB Guessed the password with 48 queries.
4 Correct 1 ms 256 KB Guessed the password with 90 queries.
5 Correct 2 ms 256 KB Guessed the password with 170 queries.
6 Correct 3 ms 256 KB Guessed the password with 198 queries.
7 Correct 46 ms 256 KB Guessed the password with 3824 queries.
8 Correct 53 ms 376 KB Guessed the password with 4971 queries.
9 Correct 79 ms 376 KB Guessed the password with 6557 queries.
10 Correct 124 ms 384 KB Guessed the password with 9000 queries.
11 Correct 166 ms 508 KB Guessed the password with 11299 queries.
12 Correct 186 ms 508 KB Guessed the password with 13424 queries.
13 Correct 223 ms 512 KB Guessed the password with 13414 queries.
14 Correct 178 ms 376 KB Guessed the password with 14652 queries.
15 Correct 166 ms 384 KB Guessed the password with 13401 queries.
16 Correct 227 ms 392 KB Guessed the password with 15312 queries.
17 Correct 238 ms 384 KB Guessed the password with 13666 queries.
18 Correct 195 ms 504 KB Guessed the password with 16182 queries.
19 Correct 234 ms 384 KB Guessed the password with 13552 queries.
20 Correct 187 ms 384 KB Guessed the password with 15702 queries.
21 Correct 237 ms 392 KB Guessed the password with 14882 queries.
22 Correct 202 ms 388 KB Guessed the password with 16691 queries.
23 Correct 388 ms 536 KB Guessed the password with 23987 queries.
24 Correct 383 ms 408 KB Guessed the password with 23318 queries.
25 Correct 344 ms 528 KB Guessed the password with 24020 queries.
26 Correct 405 ms 588 KB Guessed the password with 23431 queries.
27 Correct 348 ms 404 KB Guessed the password with 24196 queries.
28 Correct 328 ms 412 KB Guessed the password with 22391 queries.
29 Correct 335 ms 404 KB Guessed the password with 24260 queries.
30 Correct 351 ms 400 KB Guessed the password with 22365 queries.