Submission #308666

#	Time	Username	Problem	Language	Result	Execution time	Memory
308666		bigDuck	Password (RMI18_password)	C++14	30 / 100	485 ms	376 KiB

password

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20