Submission #755962

#	Time	Username	Problem	Language	Result	Execution time	Memory
755962		vjudge1	Password (RMI18_password)	C++17	100 / 100	316 ms	712 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, k = 1;
int occ[64], rem[64];
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 compare(int a, int b)
{
    if(rem[a] <= 0)
        return b;
    if(rem[b] <= 0)
        return a;
    string t= cur;
    t += (char) ('a' + a);
    for(int u = 0; u < rem[b]; u++)
        t += (char)('a' + b);
    //cout << (char)('a' + a) << ' ' << (char)('a' +b) << ' ' << rem[a] << ' ' << rem[b] << '\n';
    if(query(t) == (int)(t.length()))
        return a;
    else
        return b;
}
vi st;
void build(int p, int l, int r)
{
    if(l == r)
    {
        st[p] = l;
        return ;
    }
    build(2 * p, l, (l  + r)/2);
    build(2 * p + 1, (l + r)/2 + 1, r);
    st[p] = compare(st[2 * p], st[2 * p + 1]);
    return ;
}
void update(int i)
{
    i += k;
    i /= 2;
    while(i)
    {
        st[i] = compare(st[2 * i], st[2 * i + 1]);
        i /= 2;
    }
}
string guess(int N, int S)
{
    n = N, s = S;
    while(k < s)
        k = (k << 1);
    st.assign(2 * k + 1, 0);
    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;
    }
    build(1, 0, k - 1);
    for(int i = 0; i < N; i++)
    {
        cur += (char)('a' + st[1]);
        rem[st[1]]--;
        update(st[1]);
    }
    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: 30 / 30
• Subtask 5: 20 / 20