Submission #226966

#	Time	Username	Problem	Language	Result	Execution time	Memory
226966		qkxwsm	Password (RMI18_password)	C++14	80 / 100	639 ms	776 KiB

password

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 30 / 30
• Subtask 5: 0 / 20