oj.uz

Submission #248785

# Submission time Handle Problem Language Result Execution time Memory
248785 2020-07-13T11:45:10 Z egekabas Password (RMI18_password) C++14
100 / 100
 262 ms 728 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int query(string s);
int N;
string calc(int l, int r){
    if(l == r){
        string tmp;
        for(int i = 0; i < N; ++i)
            tmp.pb('a'+l);
        int cnt = query(tmp);
        return tmp.substr(0, cnt);
    }
    else{
        int m = (l+r)/2;
        string s1 = calc(l, m);
        string s2 = calc(m+1, r);
        string s;
        reverse(s1.begin(), s1.end());
        while(s1.size() || s2.size()){
            if(s1.empty()){
                s += s2;
                break;
            }
            if(s2.empty()){
                reverse(s1.begin(), s1.end());
                s += s1;
                break;
            }
            if(query(s+s1.back()+s2) == s.size()+s2.size()+1){
                s += s1.back();
                s1.pop_back();
            }
            else{
                reverse(s2.begin(), s2.end());
                s += s2.back();
                s2.pop_back();
                reverse(s2.begin(), s2.end());
            }
        }
        return s;
    }
}

string guess(int n, int s){
    N = n;
    return calc(0, s-1);
}

Compilation message

password.cpp: In function 'std::__cxx11::string calc(int, int)':
password.cpp:40:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(query(s+s1.back()+s2) == s.size()+s2.size()+1){
                ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 61 queries.
2 Correct 2 ms 256 KB Guessed the password with 101 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 49 queries.
2 Correct 1 ms 256 KB Guessed the password with 117 queries.
3 Correct 1 ms 256 KB Guessed the password with 92 queries.
4 Correct 2 ms 256 KB Guessed the password with 197 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 256 KB Guessed the password with 3456 queries.
2 Correct 45 ms 256 KB Guessed the password with 5025 queries.
3 Correct 56 ms 376 KB Guessed the password with 6352 queries.
4 Correct 95 ms 384 KB Guessed the password with 8693 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 61 queries.
2 Correct 2 ms 256 KB Guessed the password with 101 queries.
3 Correct 1 ms 256 KB Guessed the password with 49 queries.
4 Correct 1 ms 256 KB Guessed the password with 117 queries.
5 Correct 1 ms 256 KB Guessed the password with 92 queries.
6 Correct 2 ms 256 KB Guessed the password with 197 queries.
7 Correct 41 ms 256 KB Guessed the password with 3456 queries.
8 Correct 45 ms 256 KB Guessed the password with 5025 queries.
9 Correct 56 ms 376 KB Guessed the password with 6352 queries.
10 Correct 95 ms 384 KB Guessed the password with 8693 queries.
11 Correct 140 ms 384 KB Guessed the password with 13638 queries.
12 Correct 155 ms 380 KB Guessed the password with 12459 queries.
13 Correct 137 ms 376 KB Guessed the password with 14392 queries.
14 Correct 132 ms 376 KB Guessed the password with 13937 queries.
15 Correct 146 ms 504 KB Guessed the password with 15073 queries.
16 Correct 162 ms 508 KB Guessed the password with 14154 queries.
17 Correct 162 ms 504 KB Guessed the password with 16054 queries.
18 Correct 153 ms 384 KB Guessed the password with 15189 queries.
19 Correct 175 ms 508 KB Guessed the password with 16410 queries.
20 Correct 159 ms 504 KB Guessed the password with 14247 queries.
21 Correct 185 ms 504 KB Guessed the password with 16849 queries.
22 Correct 206 ms 508 KB Guessed the password with 15315 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 61 queries.
2 Correct 2 ms 256 KB Guessed the password with 101 queries.
3 Correct 1 ms 256 KB Guessed the password with 49 queries.
4 Correct 1 ms 256 KB Guessed the password with 117 queries.
5 Correct 1 ms 256 KB Guessed the password with 92 queries.
6 Correct 2 ms 256 KB Guessed the password with 197 queries.
7 Correct 41 ms 256 KB Guessed the password with 3456 queries.
8 Correct 45 ms 256 KB Guessed the password with 5025 queries.
9 Correct 56 ms 376 KB Guessed the password with 6352 queries.
10 Correct 95 ms 384 KB Guessed the password with 8693 queries.
11 Correct 140 ms 384 KB Guessed the password with 13638 queries.
12 Correct 155 ms 380 KB Guessed the password with 12459 queries.
13 Correct 137 ms 376 KB Guessed the password with 14392 queries.
14 Correct 132 ms 376 KB Guessed the password with 13937 queries.
15 Correct 146 ms 504 KB Guessed the password with 15073 queries.
16 Correct 162 ms 508 KB Guessed the password with 14154 queries.
17 Correct 162 ms 504 KB Guessed the password with 16054 queries.
18 Correct 153 ms 384 KB Guessed the password with 15189 queries.
19 Correct 175 ms 508 KB Guessed the password with 16410 queries.
20 Correct 159 ms 504 KB Guessed the password with 14247 queries.
21 Correct 185 ms 504 KB Guessed the password with 16849 queries.
22 Correct 206 ms 508 KB Guessed the password with 15315 queries.
23 Correct 261 ms 608 KB Guessed the password with 23612 queries.
24 Correct 216 ms 424 KB Guessed the password with 22226 queries.
25 Correct 207 ms 508 KB Guessed the password with 23794 queries.
26 Correct 241 ms 540 KB Guessed the password with 23332 queries.
27 Correct 262 ms 560 KB Guessed the password with 23763 queries.
28 Correct 238 ms 684 KB Guessed the password with 23045 queries.
29 Correct 250 ms 436 KB Guessed the password with 23847 queries.
30 Correct 220 ms 728 KB Guessed the password with 22506 queries.