Submission #226984

#	Time	Username	Problem	Language	Result	Execution time	Memory
226984		qkxwsm	Password (RMI18_password)	C++14	100 / 100	479 ms	816 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;
}

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