oj.uz

Submission #755732

# Submission time Handle Problem Language Result Execution time Memory
755732 2023-06-10T15:32:15 Z vjudge1 Password (RMI18_password) C++17
50 / 100
 413 ms 456 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;
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];
    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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 121 queries.
2 Correct 3 ms 208 KB Guessed the password with 277 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 133 queries.
3 Correct 2 ms 208 KB Guessed the password with 169 queries.
4 Correct 4 ms 208 KB Guessed the password with 292 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 308 KB Guessed the password with 9609 queries.
2 Correct 189 ms 456 KB Guessed the password with 17345 queries.
3 Correct 169 ms 328 KB Guessed the password with 21756 queries.
4 Correct 346 ms 324 KB Guessed the password with 36498 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 121 queries.
2 Correct 3 ms 208 KB Guessed the password with 277 queries.
3 Correct 1 ms 208 KB Guessed the password with 49 queries.
4 Correct 2 ms 208 KB Guessed the password with 133 queries.
5 Correct 2 ms 208 KB Guessed the password with 169 queries.
6 Correct 4 ms 208 KB Guessed the password with 292 queries.
7 Correct 82 ms 308 KB Guessed the password with 9609 queries.
8 Correct 189 ms 456 KB Guessed the password with 17345 queries.
9 Correct 169 ms 328 KB Guessed the password with 21756 queries.
10 Correct 346 ms 324 KB Guessed the password with 36498 queries.
11 Incorrect 413 ms 452 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 121 queries.
2 Correct 3 ms 208 KB Guessed the password with 277 queries.
3 Correct 1 ms 208 KB Guessed the password with 49 queries.
4 Correct 2 ms 208 KB Guessed the password with 133 queries.
5 Correct 2 ms 208 KB Guessed the password with 169 queries.
6 Correct 4 ms 208 KB Guessed the password with 292 queries.
7 Correct 82 ms 308 KB Guessed the password with 9609 queries.
8 Correct 189 ms 456 KB Guessed the password with 17345 queries.
9 Correct 169 ms 328 KB Guessed the password with 21756 queries.
10 Correct 346 ms 324 KB Guessed the password with 36498 queries.
11 Incorrect 413 ms 452 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -