oj.uz

Submission #308666

# Submission time Handle Problem Language Result Execution time Memory
308666 2020-10-01T16:46:49 Z bigDuck Password (RMI18_password) C++14
30 / 100
 485 ms 376 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
//#define int ll


int query(string str);




int bs(char c, string s, int n){

int l=0, r=n-s.length(), m=(l+r)/2;

while(l<r){
    m=(l+r)/2;
    string s0="";
    for(int i=1; i<=m; i++){ s0+="a"; s0[s0.length()-1]+=(c-'a');}
    string s2=s0+s;
    int ln=query(s2);
    if(ln!=(s2.length())){
        r=m;
    }
    else{
        l=(m+1);
    }
    m=(l+r)/2;
}
    string s0="";
    for(int i=1; i<=m; i++){ s0+="a"; s0[s0.length()-1]+=(c-'a');}
    string s2=s0+s;
    int ln=query(s2);
    if(ln!=(s2.length())){m--;}
    return m;
}





int cnt[300];

void get_cnt(int n, int s){
    for(char c1='a'; c1<=('a'+s-1); c1++){
        string st;
        for(int i=1; i<=n; i++){
            st+="a"; st[st.length()-1 ]+=(c1-'a');
        }
        int ln=query(st);
        cnt[c1]=ln;
    }
}


string guess(int n, int s){
string suf="";
get_cnt(n, s);



while( (suf.length())<n ){
    int sz[300]; memset(sz, 0, sizeof(sz));
    for(char c1='a'; c1<=('a'+s-1); c1++){
        if(cnt[c1]==0){continue;}
        for(char c2='a'; c2<=('a'+s-1); c2++){
            if(cnt[c2]==0){
                continue;
            }
            string st; st="a"; st[0]+=(c1-'a'); st+=suf;
            sz[c1]+=bs(c2, st, n);
        }
    }
    int mx=0; char mc='a';
    for(char c1='a'; c1<='z'; c1++){
        if(sz[c1]>mx){
            mc=c1; mx=sz[c1];
        }
    }
    suf="a"+suf; suf[0]+=(mc-'a'); cnt[mc]--;
}

return suf;
}

Compilation message

password.cpp: In function 'int bs(char, std::string, int)':
password.cpp:29:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     if(ln!=(s2.length())){
      |        ~~^~~~~~~~~~~~~~~
password.cpp:41:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     if(ln!=(s2.length())){m--;}
      |        ~~^~~~~~~~~~~~~~~
password.cpp: In function 'void get_cnt(int, int)':
password.cpp:58:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   58 |         cnt[c1]=ln;
      |             ^~
password.cpp: In function 'std::string guess(int, int)':
password.cpp:69:22: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 | while( (suf.length())<n ){
      |        ~~~~~~~~~~~~~~^~
password.cpp:72:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   72 |         if(cnt[c1]==0){continue;}
      |                ^~
password.cpp:74:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   74 |             if(cnt[c2]==0){
      |                    ^~
password.cpp:78:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   78 |             sz[c1]+=bs(c2, st, n);
      |                ^~
password.cpp:83:15: warning: array subscript has type 'char' [-Wchar-subscripts]
   83 |         if(sz[c1]>mx){
      |               ^~
password.cpp:84:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   84 |             mc=c1; mx=sz[c1];
      |                          ^~
password.cpp:87:40: warning: array subscript has type 'char' [-Wchar-subscripts]
   87 |     suf="a"+suf; suf[0]+=(mc-'a'); cnt[mc]--;
      |                                        ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 256 KB Guessed the password with 5740 queries.
2 Correct 208 ms 256 KB Guessed the password with 22652 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 256 KB Guessed the password with 1018 queries.
2 Correct 37 ms 256 KB Guessed the password with 3576 queries.
3 Correct 6 ms 256 KB Guessed the password with 429 queries.
4 Correct 97 ms 376 KB Guessed the password with 9953 queries.

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 485 ms 256 KB Could not guess the password with 50000 queries.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 256 KB Guessed the password with 5740 queries.
2 Correct 208 ms 256 KB Guessed the password with 22652 queries.
3 Correct 10 ms 256 KB Guessed the password with 1018 queries.
4 Correct 37 ms 256 KB Guessed the password with 3576 queries.
5 Correct 6 ms 256 KB Guessed the password with 429 queries.
6 Correct 97 ms 376 KB Guessed the password with 9953 queries.
7 Incorrect 485 ms 256 KB Could not guess the password with 50000 queries.
8 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 256 KB Guessed the password with 5740 queries.
2 Correct 208 ms 256 KB Guessed the password with 22652 queries.
3 Correct 10 ms 256 KB Guessed the password with 1018 queries.
4 Correct 37 ms 256 KB Guessed the password with 3576 queries.
5 Correct 6 ms 256 KB Guessed the password with 429 queries.
6 Correct 97 ms 376 KB Guessed the password with 9953 queries.
7 Incorrect 485 ms 256 KB Could not guess the password with 50000 queries.
8 Halted 0 ms 0 KB -