Submission #226969

#	Time	Username	Problem	Language	Result	Execution time	Memory
226969		qkxwsm	Password (RMI18_password)	C++14	80 / 100	601 ms	648 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;
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);
    sort(ALL(ord), cmp);
    FOR(i, 0, S)
    {
        char ch = ('a' + ord[i]);
        int freq = dp[ord[i]];
        int iter = 0;
        while(freq > 0)
        {
            string tmp = res;
            tmp.insert(tmp.begin() + iter, ch);
            if (query(tmp) == SZ(tmp))
            {
                res = tmp;
                freq--;
            }
            iter++;
        }
    }
    return res;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 30 / 30
• Subtask 5: 0 / 20