oj.uz

Submission #755962

# Submission time Handle Problem Language Result Execution time Memory
755962 2023-06-10T18:33:34 Z vjudge1 Password (RMI18_password) C++17
100 / 100
 316 ms 712 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 61 queries.
2 Correct 2 ms 208 KB Guessed the password with 103 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 49 queries.
2 Correct 2 ms 208 KB Guessed the password with 117 queries.
3 Correct 1 ms 208 KB Guessed the password with 91 queries.
4 Correct 2 ms 208 KB Guessed the password with 197 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 420 KB Guessed the password with 3473 queries.
2 Correct 56 ms 324 KB Guessed the password with 5025 queries.
3 Correct 55 ms 328 KB Guessed the password with 6858 queries.
4 Correct 79 ms 324 KB Guessed the password with 9073 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 61 queries.
2 Correct 2 ms 208 KB Guessed the password with 103 queries.
3 Correct 1 ms 208 KB Guessed the password with 49 queries.
4 Correct 2 ms 208 KB Guessed the password with 117 queries.
5 Correct 1 ms 208 KB Guessed the password with 91 queries.
6 Correct 2 ms 208 KB Guessed the password with 197 queries.
7 Correct 21 ms 420 KB Guessed the password with 3473 queries.
8 Correct 56 ms 324 KB Guessed the password with 5025 queries.
9 Correct 55 ms 328 KB Guessed the password with 6858 queries.
10 Correct 79 ms 324 KB Guessed the password with 9073 queries.
11 Correct 151 ms 464 KB Guessed the password with 13607 queries.
12 Correct 151 ms 452 KB Guessed the password with 11100 queries.
13 Correct 104 ms 336 KB Guessed the password with 14700 queries.
14 Correct 120 ms 456 KB Guessed the password with 13486 queries.
15 Correct 142 ms 332 KB Guessed the password with 14843 queries.
16 Correct 178 ms 340 KB Guessed the password with 13540 queries.
17 Correct 151 ms 360 KB Guessed the password with 16238 queries.
18 Correct 123 ms 460 KB Guessed the password with 13756 queries.
19 Correct 149 ms 344 KB Guessed the password with 16676 queries.
20 Correct 126 ms 456 KB Guessed the password with 12434 queries.
21 Correct 132 ms 584 KB Guessed the password with 17141 queries.
22 Correct 116 ms 584 KB Guessed the password with 14499 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 61 queries.
2 Correct 2 ms 208 KB Guessed the password with 103 queries.
3 Correct 1 ms 208 KB Guessed the password with 49 queries.
4 Correct 2 ms 208 KB Guessed the password with 117 queries.
5 Correct 1 ms 208 KB Guessed the password with 91 queries.
6 Correct 2 ms 208 KB Guessed the password with 197 queries.
7 Correct 21 ms 420 KB Guessed the password with 3473 queries.
8 Correct 56 ms 324 KB Guessed the password with 5025 queries.
9 Correct 55 ms 328 KB Guessed the password with 6858 queries.
10 Correct 79 ms 324 KB Guessed the password with 9073 queries.
11 Correct 151 ms 464 KB Guessed the password with 13607 queries.
12 Correct 151 ms 452 KB Guessed the password with 11100 queries.
13 Correct 104 ms 336 KB Guessed the password with 14700 queries.
14 Correct 120 ms 456 KB Guessed the password with 13486 queries.
15 Correct 142 ms 332 KB Guessed the password with 14843 queries.
16 Correct 178 ms 340 KB Guessed the password with 13540 queries.
17 Correct 151 ms 360 KB Guessed the password with 16238 queries.
18 Correct 123 ms 460 KB Guessed the password with 13756 queries.
19 Correct 149 ms 344 KB Guessed the password with 16676 queries.
20 Correct 126 ms 456 KB Guessed the password with 12434 queries.
21 Correct 132 ms 584 KB Guessed the password with 17141 queries.
22 Correct 116 ms 584 KB Guessed the password with 14499 queries.
23 Correct 244 ms 340 KB Guessed the password with 24023 queries.
24 Correct 237 ms 448 KB Guessed the password with 22706 queries.
25 Correct 238 ms 712 KB Guessed the password with 24096 queries.
26 Correct 316 ms 584 KB Guessed the password with 24565 queries.
27 Correct 236 ms 576 KB Guessed the password with 24136 queries.
28 Correct 223 ms 492 KB Guessed the password with 23569 queries.
29 Correct 251 ms 572 KB Guessed the password with 24180 queries.
30 Correct 186 ms 540 KB Guessed the password with 22392 queries.