oj.uz

Submission #519407

# Submission time Handle Problem Language Result Execution time Memory
519407 2022-01-26T10:22:07 Z hohohaha Password (RMI18_password) C++14
100 / 100
 263 ms 656 KB 
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
 
//using namespace __gnu_pbds;
using namespace std;
 
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld, ld> pld;
typedef vector<pi> vpi;
 
string substr(string s, int l, int r) {
    string ans;
    for (int i = l; i <= r; i++)
        ans += s[i];
    return ans;
}
 
int query(string);
 
vi cnt;
 
string merge(string s,string t){
    if(s.size()<t.size())
        swap(s,t);
    for(int i=-1; i<int(s.size()); i++){
        if(!t.size())break;
        string cur=s.substr(0,i+1)+string(1,t[0])+s.substr(i+1,s.size()-(i+1));
        if(query(cur)==cur.size()){
            s=s.substr(0,i+1)+string(1,t[0])+s.substr(i+1,s.size()-(i+1));
            t=t.substr(1,t.size()-1);
        }
    }
    return s;
}
string dfs(int l,int r,int n){
    if(l>r)return "";
    else if(l==r)return string(cnt[l],l+'a');
 
    int m=(l+r)/2;
    return merge(dfs(l,m,n),dfs(m+1,r,n));
}
string guess(int n,int AB){
    cnt=vi(26);
    int sum=0;
    for(int i=0; i<AB; i++){
        int ans=query(string(n,i+'a'));
        cnt[i]=ans;
        sum+=ans;
    }
    return dfs(0,AB-1,n);
}

Compilation message

password.cpp: In function 'std::string merge(std::string, std::string)':
password.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         if(query(cur)==cur.size()){
      |            ~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 68 queries.
2 Correct 1 ms 200 KB Guessed the password with 111 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 52 queries.
2 Correct 1 ms 200 KB Guessed the password with 116 queries.
3 Correct 2 ms 200 KB Guessed the password with 105 queries.
4 Correct 2 ms 200 KB Guessed the password with 199 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 372 KB Guessed the password with 3462 queries.
2 Correct 24 ms 376 KB Guessed the password with 5035 queries.
3 Correct 68 ms 500 KB Guessed the password with 6355 queries.
4 Correct 85 ms 384 KB Guessed the password with 8715 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 68 queries.
2 Correct 1 ms 200 KB Guessed the password with 111 queries.
3 Correct 1 ms 200 KB Guessed the password with 52 queries.
4 Correct 1 ms 200 KB Guessed the password with 116 queries.
5 Correct 2 ms 200 KB Guessed the password with 105 queries.
6 Correct 2 ms 200 KB Guessed the password with 199 queries.
7 Correct 37 ms 372 KB Guessed the password with 3462 queries.
8 Correct 24 ms 376 KB Guessed the password with 5035 queries.
9 Correct 68 ms 500 KB Guessed the password with 6355 queries.
10 Correct 85 ms 384 KB Guessed the password with 8715 queries.
11 Correct 142 ms 400 KB Guessed the password with 13650 queries.
12 Correct 124 ms 504 KB Guessed the password with 12460 queries.
13 Correct 172 ms 452 KB Guessed the password with 14407 queries.
14 Correct 136 ms 520 KB Guessed the password with 13973 queries.
15 Correct 169 ms 524 KB Guessed the password with 15077 queries.
16 Correct 116 ms 328 KB Guessed the password with 14160 queries.
17 Correct 147 ms 524 KB Guessed the password with 16061 queries.
18 Correct 125 ms 396 KB Guessed the password with 15212 queries.
19 Correct 110 ms 396 KB Guessed the password with 16417 queries.
20 Correct 184 ms 384 KB Guessed the password with 14253 queries.
21 Correct 235 ms 400 KB Guessed the password with 16875 queries.
22 Correct 149 ms 516 KB Guessed the password with 15478 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 68 queries.
2 Correct 1 ms 200 KB Guessed the password with 111 queries.
3 Correct 1 ms 200 KB Guessed the password with 52 queries.
4 Correct 1 ms 200 KB Guessed the password with 116 queries.
5 Correct 2 ms 200 KB Guessed the password with 105 queries.
6 Correct 2 ms 200 KB Guessed the password with 199 queries.
7 Correct 37 ms 372 KB Guessed the password with 3462 queries.
8 Correct 24 ms 376 KB Guessed the password with 5035 queries.
9 Correct 68 ms 500 KB Guessed the password with 6355 queries.
10 Correct 85 ms 384 KB Guessed the password with 8715 queries.
11 Correct 142 ms 400 KB Guessed the password with 13650 queries.
12 Correct 124 ms 504 KB Guessed the password with 12460 queries.
13 Correct 172 ms 452 KB Guessed the password with 14407 queries.
14 Correct 136 ms 520 KB Guessed the password with 13973 queries.
15 Correct 169 ms 524 KB Guessed the password with 15077 queries.
16 Correct 116 ms 328 KB Guessed the password with 14160 queries.
17 Correct 147 ms 524 KB Guessed the password with 16061 queries.
18 Correct 125 ms 396 KB Guessed the password with 15212 queries.
19 Correct 110 ms 396 KB Guessed the password with 16417 queries.
20 Correct 184 ms 384 KB Guessed the password with 14253 queries.
21 Correct 235 ms 400 KB Guessed the password with 16875 queries.
22 Correct 149 ms 516 KB Guessed the password with 15478 queries.
23 Correct 190 ms 528 KB Guessed the password with 23705 queries.
24 Correct 263 ms 592 KB Guessed the password with 22240 queries.
25 Correct 165 ms 608 KB Guessed the password with 23865 queries.
26 Correct 225 ms 532 KB Guessed the password with 23349 queries.
27 Correct 220 ms 536 KB Guessed the password with 23792 queries.
28 Correct 261 ms 656 KB Guessed the password with 23049 queries.
29 Correct 242 ms 528 KB Guessed the password with 23871 queries.
30 Correct 226 ms 484 KB Guessed the password with 22509 queries.