Submission #755938

#	Time	Username	Problem	Language	Result	Execution time	Memory
755938		vjudge1	Password (RMI18_password)	C++17	50 / 100	788 ms	584 KiB

password

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
const ll MOD = 1e9 + 7;
ll mod(ll x, ll m = MOD){return (x + m) % m;}

typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;

typedef vector<pair<int,int>> vpi;

#define pb push_back

#define ff first
#define ss second
#define all(x) (x).begin(),(x).end()

int n, s;
int occ[26], rem[26];
string cur = "";
int query(string str);
string guess(int n, int s);

/*
string STR;
int query(string t)
{
    int cur = 0;
    for(int i =0; i < n; i++)
    {
        if(t[cur] == STR[i])
            cur++;
    }
    return cur;
}
*/

int win(vi L)
{

    int sz = L.size();
    if(sz == 1)
        return L[0];
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    shuffle(all(L), rng);
    vi L1, L2;
    for(int i = 0; i < sz/2; i++)
        L1.pb(L[i]);
    for(int i = sz/2; i < sz; i++)
        L2.pb(L[i]);
    int w1 = win(L1);
    int w2 = win(L2);
    string t =  cur;
    t += (char)('a' + w1);
    for(int u = 0; u < rem[w2]; u++)
        t += (char)('a' + w2);
    int rep = query(t);
    if(rep == (int)(t.length()))
        return w1;
    else
        return w2;
}
string guess(int N, int S)
{
    n = N, s = S;
    for(int l = 0; l < s; l++)
    {
        string t=  "";
        for(int i = 0; i < N; i++)
            t += (char)('a' + l);
        occ[l] = query(t);
        rem[l] = occ[l];
        if(occ[l] == N)
            return t;
    }
    vi let;
    for(int i = 0; i < N; i++)
    {
        let.clear();
        for(int l=  0; l <s;l ++)
            if(rem[l])
                let.pb(l);
        int idx = win(let);
        rem[idx]--;
        cur += (char)('a' + idx);
    }
    return cur;
}
/*
int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int N, S;
    cin >> N >> S;
    cin >> STR;
    cout << guess(N, S);

}
*/

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