oj.uz

Submission #709358

# Submission time Handle Problem Language Result Execution time Memory
709358 2023-03-13T13:17:32 Z maomao90 Password (RMI18_password) C++17
100 / 100
 249 ms 612 KB 
// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;

#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 5005;

int query(string str);

int occ[30];

string dnc(int l, int r) {
    if (l == r) {
        return string(occ[l], 'a' + l);
    }
    int m = l + r >> 1;
    string sl = dnc(l, m), sr = dnc(m + 1, r);
    string str = sl;
    int ptr = 0;
    REP (i, 0, SZ(sr)) {
        str.insert(ptr, 1, sr[i]);
        while (query(str) != SZ(str)) {
            str.erase(ptr, 1);
            ptr++;
            str.insert(ptr, 1, sr[i]);
        }
        ptr++;
    }
    return str;
}

string guess(int n, int s) {
    REP (c, 0, s) {
        string str(n, 'a' + c);
        occ[c] = query(str);
    }
    string ans = dnc(0, s - 1);
    return ans;
}

Compilation message

password.cpp: In function 'std::string dnc(int, int)':
password.cpp:46:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     int m = l + r >> 1;
      |             ~~^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 48 queries.
2 Correct 2 ms 208 KB Guessed the password with 116 queries.
3 Correct 1 ms 208 KB Guessed the password with 93 queries.
4 Correct 2 ms 208 KB Guessed the password with 203 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 312 KB Guessed the password with 3704 queries.
2 Correct 57 ms 300 KB Guessed the password with 5053 queries.
3 Correct 59 ms 324 KB Guessed the password with 6584 queries.
4 Correct 88 ms 324 KB Guessed the password with 8721 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 68 queries.
2 Correct 2 ms 208 KB Guessed the password with 111 queries.
3 Correct 1 ms 208 KB Guessed the password with 48 queries.
4 Correct 2 ms 208 KB Guessed the password with 116 queries.
5 Correct 1 ms 208 KB Guessed the password with 93 queries.
6 Correct 2 ms 208 KB Guessed the password with 203 queries.
7 Correct 32 ms 312 KB Guessed the password with 3704 queries.
8 Correct 57 ms 300 KB Guessed the password with 5053 queries.
9 Correct 59 ms 324 KB Guessed the password with 6584 queries.
10 Correct 88 ms 324 KB Guessed the password with 8721 queries.
11 Correct 135 ms 328 KB Guessed the password with 13682 queries.
12 Correct 126 ms 420 KB Guessed the password with 12654 queries.
13 Correct 137 ms 332 KB Guessed the password with 14410 queries.
14 Correct 139 ms 328 KB Guessed the password with 13979 queries.
15 Correct 122 ms 436 KB Guessed the password with 15314 queries.
16 Correct 142 ms 328 KB Guessed the password with 14485 queries.
17 Correct 122 ms 576 KB Guessed the password with 16114 queries.
18 Correct 154 ms 460 KB Guessed the password with 15294 queries.
19 Correct 127 ms 456 KB Guessed the password with 16485 queries.
20 Correct 91 ms 456 KB Guessed the password with 15088 queries.
21 Correct 170 ms 340 KB Guessed the password with 16990 queries.
22 Correct 109 ms 576 KB Guessed the password with 15908 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 68 queries.
2 Correct 2 ms 208 KB Guessed the password with 111 queries.
3 Correct 1 ms 208 KB Guessed the password with 48 queries.
4 Correct 2 ms 208 KB Guessed the password with 116 queries.
5 Correct 1 ms 208 KB Guessed the password with 93 queries.
6 Correct 2 ms 208 KB Guessed the password with 203 queries.
7 Correct 32 ms 312 KB Guessed the password with 3704 queries.
8 Correct 57 ms 300 KB Guessed the password with 5053 queries.
9 Correct 59 ms 324 KB Guessed the password with 6584 queries.
10 Correct 88 ms 324 KB Guessed the password with 8721 queries.
11 Correct 135 ms 328 KB Guessed the password with 13682 queries.
12 Correct 126 ms 420 KB Guessed the password with 12654 queries.
13 Correct 137 ms 332 KB Guessed the password with 14410 queries.
14 Correct 139 ms 328 KB Guessed the password with 13979 queries.
15 Correct 122 ms 436 KB Guessed the password with 15314 queries.
16 Correct 142 ms 328 KB Guessed the password with 14485 queries.
17 Correct 122 ms 576 KB Guessed the password with 16114 queries.
18 Correct 154 ms 460 KB Guessed the password with 15294 queries.
19 Correct 127 ms 456 KB Guessed the password with 16485 queries.
20 Correct 91 ms 456 KB Guessed the password with 15088 queries.
21 Correct 170 ms 340 KB Guessed the password with 16990 queries.
22 Correct 109 ms 576 KB Guessed the password with 15908 queries.
23 Correct 143 ms 460 KB Guessed the password with 23708 queries.
24 Correct 146 ms 468 KB Guessed the password with 22770 queries.
25 Correct 225 ms 612 KB Guessed the password with 23853 queries.
26 Correct 161 ms 388 KB Guessed the password with 23374 queries.
27 Correct 182 ms 576 KB Guessed the password with 23807 queries.
28 Correct 200 ms 588 KB Guessed the password with 23436 queries.
29 Correct 175 ms 472 KB Guessed the password with 23873 queries.
30 Correct 249 ms 528 KB Guessed the password with 23818 queries.