oj.uz

Submission #226984

# Submission time Handle Problem Language Result Execution time Memory
226984 2020-04-25T19:26:56 Z qkxwsm Password (RMI18_password) C++14
100 / 100
 479 ms 816 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;
}

random_device rd;
mt19937 rng(rd());
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;
vi dp, ord;

int query(string str);

bool cmp(int i, int j)
{
    return dp[i] < dp[j];
}
string guess(int n, int s)
{
    N = n; S = s;
    dp.resize(S); ord.resize(S);
    string res = "";
    FOR(i, 0, S)
    {
        char ch = ('a' + i);
        dp[i] = query(string(N, ch));
    }
    iota(ALL(ord), 0);
    // FOR(i, 1, SZ(ord))
    // {
    //     swap(ord[i], ord[randomize(i + 1)]);
    // }
    sort(ALL(ord), cmp);
    FOR(i, 0, S / 2)
    {
        char ch = ('a' + ord[i]);
        int freq = dp[ord[i]];
        if (i == 0)
        {
            res = string(freq, ch);
            continue;
        }
        int iter = 0;
        while(freq > 0)
        {
            string tmp = res;
            tmp.insert(tmp.begin() + iter, ch);
            if (query(tmp) == SZ(tmp))
            {
                res = tmp;
                freq--;
            }
            iter++;
        }
    }
    string part1 = res;
    res = "";
    FOR(i, S / 2, S)
    {
        char ch = ('a' + ord[i]);
        int freq = dp[ord[i]];
        if (i == S / 2)
        {
            res = string(freq, ch);
            continue;
        }
        int iter = 0;
        while(freq > 0)
        {
            string tmp = res;
            tmp.insert(tmp.begin() + iter, ch);
            if (query(tmp) == SZ(tmp))
            {
                res = tmp;
                freq--;
            }
            iter++;
        }
    }
    //try inserting part1 into part2
    int iter = 0, pos = 0;
    while(pos != SZ(part1))
    {
        char ch = part1[pos];
        string tmp = res;
        tmp.insert(tmp.begin() + iter, ch);
        if (query(tmp) == SZ(tmp))
        {
            res = tmp;
            pos++;
        }
        iter++;
    }
    return res;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Guessed the password with 62 queries.
2 Correct 6 ms 256 KB Guessed the password with 133 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Guessed the password with 52 queries.
2 Correct 6 ms 384 KB Guessed the password with 134 queries.
3 Correct 6 ms 384 KB Guessed the password with 171 queries.
4 Correct 6 ms 384 KB Guessed the password with 204 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 384 KB Guessed the password with 3777 queries.
2 Correct 67 ms 384 KB Guessed the password with 6469 queries.
3 Correct 71 ms 384 KB Guessed the password with 6517 queries.
4 Correct 117 ms 376 KB Guessed the password with 11157 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Guessed the password with 62 queries.
2 Correct 6 ms 256 KB Guessed the password with 133 queries.
3 Correct 5 ms 256 KB Guessed the password with 52 queries.
4 Correct 6 ms 384 KB Guessed the password with 134 queries.
5 Correct 6 ms 384 KB Guessed the password with 171 queries.
6 Correct 6 ms 384 KB Guessed the password with 204 queries.
7 Correct 43 ms 384 KB Guessed the password with 3777 queries.
8 Correct 67 ms 384 KB Guessed the password with 6469 queries.
9 Correct 71 ms 384 KB Guessed the password with 6517 queries.
10 Correct 117 ms 376 KB Guessed the password with 11157 queries.
11 Correct 126 ms 384 KB Guessed the password with 11982 queries.
12 Correct 116 ms 384 KB Guessed the password with 11934 queries.
13 Correct 183 ms 388 KB Guessed the password with 18525 queries.
14 Correct 192 ms 632 KB Guessed the password with 18641 queries.
15 Correct 154 ms 548 KB Guessed the password with 17108 queries.
16 Correct 187 ms 632 KB Guessed the password with 16962 queries.
17 Correct 164 ms 480 KB Guessed the password with 15146 queries.
18 Correct 162 ms 512 KB Guessed the password with 15281 queries.
19 Correct 155 ms 384 KB Guessed the password with 14036 queries.
20 Correct 160 ms 392 KB Guessed the password with 13295 queries.
21 Correct 182 ms 508 KB Guessed the password with 18288 queries.
22 Correct 179 ms 396 KB Guessed the password with 17588 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Guessed the password with 62 queries.
2 Correct 6 ms 256 KB Guessed the password with 133 queries.
3 Correct 5 ms 256 KB Guessed the password with 52 queries.
4 Correct 6 ms 384 KB Guessed the password with 134 queries.
5 Correct 6 ms 384 KB Guessed the password with 171 queries.
6 Correct 6 ms 384 KB Guessed the password with 204 queries.
7 Correct 43 ms 384 KB Guessed the password with 3777 queries.
8 Correct 67 ms 384 KB Guessed the password with 6469 queries.
9 Correct 71 ms 384 KB Guessed the password with 6517 queries.
10 Correct 117 ms 376 KB Guessed the password with 11157 queries.
11 Correct 126 ms 384 KB Guessed the password with 11982 queries.
12 Correct 116 ms 384 KB Guessed the password with 11934 queries.
13 Correct 183 ms 388 KB Guessed the password with 18525 queries.
14 Correct 192 ms 632 KB Guessed the password with 18641 queries.
15 Correct 154 ms 548 KB Guessed the password with 17108 queries.
16 Correct 187 ms 632 KB Guessed the password with 16962 queries.
17 Correct 164 ms 480 KB Guessed the password with 15146 queries.
18 Correct 162 ms 512 KB Guessed the password with 15281 queries.
19 Correct 155 ms 384 KB Guessed the password with 14036 queries.
20 Correct 160 ms 392 KB Guessed the password with 13295 queries.
21 Correct 182 ms 508 KB Guessed the password with 18288 queries.
22 Correct 179 ms 396 KB Guessed the password with 17588 queries.
23 Correct 367 ms 816 KB Guessed the password with 38502 queries.
24 Correct 323 ms 592 KB Guessed the password with 33036 queries.
25 Correct 371 ms 416 KB Guessed the password with 38586 queries.
26 Correct 350 ms 636 KB Guessed the password with 30785 queries.
27 Correct 472 ms 520 KB Guessed the password with 38862 queries.
28 Correct 317 ms 656 KB Guessed the password with 26317 queries.
29 Correct 479 ms 528 KB Guessed the password with 38674 queries.
30 Correct 286 ms 476 KB Guessed the password with 20858 queries.