oj.uz

Submission #226964

# Submission time Handle Problem Language Result Execution time Memory
226964 2020-04-25T18:33:44 Z qkxwsm Password (RMI18_password) C++14
50 / 100
 600 ms 416 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;
    string res = "";
    FOR(i, 0, S)
    {
        char ch = ('a' + 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 384 KB Guessed the password with 77 queries.
2 Correct 6 ms 256 KB Guessed the password with 188 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Guessed the password with 72 queries.
2 Correct 6 ms 256 KB Guessed the password with 164 queries.
3 Correct 5 ms 256 KB Guessed the password with 103 queries.
4 Correct 7 ms 384 KB Guessed the password with 229 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 376 KB Guessed the password with 4581 queries.
2 Correct 93 ms 376 KB Guessed the password with 10303 queries.
3 Correct 155 ms 376 KB Guessed the password with 12561 queries.
4 Correct 272 ms 380 KB Guessed the password with 20501 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Guessed the password with 77 queries.
2 Correct 6 ms 256 KB Guessed the password with 188 queries.
3 Correct 6 ms 384 KB Guessed the password with 72 queries.
4 Correct 6 ms 256 KB Guessed the password with 164 queries.
5 Correct 5 ms 256 KB Guessed the password with 103 queries.
6 Correct 7 ms 384 KB Guessed the password with 229 queries.
7 Correct 64 ms 376 KB Guessed the password with 4581 queries.
8 Correct 93 ms 376 KB Guessed the password with 10303 queries.
9 Correct 155 ms 376 KB Guessed the password with 12561 queries.
10 Correct 272 ms 380 KB Guessed the password with 20501 queries.
11 Incorrect 600 ms 416 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Guessed the password with 77 queries.
2 Correct 6 ms 256 KB Guessed the password with 188 queries.
3 Correct 6 ms 384 KB Guessed the password with 72 queries.
4 Correct 6 ms 256 KB Guessed the password with 164 queries.
5 Correct 5 ms 256 KB Guessed the password with 103 queries.
6 Correct 7 ms 384 KB Guessed the password with 229 queries.
7 Correct 64 ms 376 KB Guessed the password with 4581 queries.
8 Correct 93 ms 376 KB Guessed the password with 10303 queries.
9 Correct 155 ms 376 KB Guessed the password with 12561 queries.
10 Correct 272 ms 380 KB Guessed the password with 20501 queries.
11 Incorrect 600 ms 416 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -