oj.uz

Submission #226966

# Submission time Handle Problem Language Result Execution time Memory
226966 2020-04-25T18:34:54 Z qkxwsm Password (RMI18_password) C++14
80 / 100
 639 ms 776 KB 
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

mt19937 rng(42);
template<class T>
T randomize(T mod)
{
    return uniform_int_distribution<T>(0, mod - 1)(rng);
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, S;

int query(string str);

string guess(int n, int s)
{
    N = n; S = s;
    vi ord(S); iota(ALL(ord), 0);
    FOR(i, 1, SZ(ord)) swap(ord[i], ord[randomize(i + 1)]);
    string res = "";
    FOR(i, 0, S)
    {
        char ch = ('a' + ord[i]);
        string str = string(N, ch);
        int freq = query(str);
        int iter = 0;
        for (int j = 0; j < freq; )
        {
            string tmp = res;
            tmp.insert(tmp.begin() + iter, ch);
            if (query(tmp) == SZ(tmp))
            {
                res = tmp;
                j++;
            }
            iter++;
        }
    }
    return res;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 256 KB Guessed the password with 89 queries.
2 Correct 6 ms 256 KB Guessed the password with 146 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Guessed the password with 78 queries.
2 Correct 6 ms 256 KB Guessed the password with 125 queries.
3 Correct 5 ms 256 KB Guessed the password with 93 queries.
4 Correct 8 ms 256 KB Guessed the password with 261 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 384 KB Guessed the password with 6796 queries.
2 Correct 122 ms 384 KB Guessed the password with 9989 queries.
3 Correct 100 ms 384 KB Guessed the password with 9911 queries.
4 Correct 246 ms 504 KB Guessed the password with 22048 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 256 KB Guessed the password with 89 queries.
2 Correct 6 ms 256 KB Guessed the password with 146 queries.
3 Correct 5 ms 256 KB Guessed the password with 78 queries.
4 Correct 6 ms 256 KB Guessed the password with 125 queries.
5 Correct 5 ms 256 KB Guessed the password with 93 queries.
6 Correct 8 ms 256 KB Guessed the password with 261 queries.
7 Correct 93 ms 384 KB Guessed the password with 6796 queries.
8 Correct 122 ms 384 KB Guessed the password with 9989 queries.
9 Correct 100 ms 384 KB Guessed the password with 9911 queries.
10 Correct 246 ms 504 KB Guessed the password with 22048 queries.
11 Correct 278 ms 392 KB Guessed the password with 26313 queries.
12 Correct 224 ms 504 KB Guessed the password with 22828 queries.
13 Correct 406 ms 508 KB Guessed the password with 37328 queries.
14 Correct 399 ms 632 KB Guessed the password with 34855 queries.
15 Correct 332 ms 504 KB Guessed the password with 32248 queries.
16 Correct 349 ms 388 KB Guessed the password with 30387 queries.
17 Correct 367 ms 504 KB Guessed the password with 31273 queries.
18 Correct 356 ms 636 KB Guessed the password with 30878 queries.
19 Correct 376 ms 484 KB Guessed the password with 31239 queries.
20 Correct 295 ms 508 KB Guessed the password with 24704 queries.
21 Correct 343 ms 388 KB Guessed the password with 33124 queries.
22 Correct 288 ms 508 KB Guessed the password with 26880 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 256 KB Guessed the password with 89 queries.
2 Correct 6 ms 256 KB Guessed the password with 146 queries.
3 Correct 5 ms 256 KB Guessed the password with 78 queries.
4 Correct 6 ms 256 KB Guessed the password with 125 queries.
5 Correct 5 ms 256 KB Guessed the password with 93 queries.
6 Correct 8 ms 256 KB Guessed the password with 261 queries.
7 Correct 93 ms 384 KB Guessed the password with 6796 queries.
8 Correct 122 ms 384 KB Guessed the password with 9989 queries.
9 Correct 100 ms 384 KB Guessed the password with 9911 queries.
10 Correct 246 ms 504 KB Guessed the password with 22048 queries.
11 Correct 278 ms 392 KB Guessed the password with 26313 queries.
12 Correct 224 ms 504 KB Guessed the password with 22828 queries.
13 Correct 406 ms 508 KB Guessed the password with 37328 queries.
14 Correct 399 ms 632 KB Guessed the password with 34855 queries.
15 Correct 332 ms 504 KB Guessed the password with 32248 queries.
16 Correct 349 ms 388 KB Guessed the password with 30387 queries.
17 Correct 367 ms 504 KB Guessed the password with 31273 queries.
18 Correct 356 ms 636 KB Guessed the password with 30878 queries.
19 Correct 376 ms 484 KB Guessed the password with 31239 queries.
20 Correct 295 ms 508 KB Guessed the password with 24704 queries.
21 Correct 343 ms 388 KB Guessed the password with 33124 queries.
22 Correct 288 ms 508 KB Guessed the password with 26880 queries.
23 Execution timed out 639 ms 776 KB Time limit exceeded (wall clock)
24 Halted 0 ms 0 KB -