oj.uz

Submission #755938

# Submission time Handle Problem Language Result Execution time Memory
755938 2023-06-10T18:02:04 Z vjudge1 Password (RMI18_password) C++17
50 / 100
 788 ms 584 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];
    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.0 / 10.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 344 KB Guessed the password with 9608 queries.
2 Correct 258 ms 456 KB Guessed the password with 17345 queries.
3 Correct 348 ms 444 KB Guessed the password with 21757 queries.
4 Correct 573 ms 584 KB Guessed the password with 36498 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 121 queries.
2 Correct 6 ms 208 KB Guessed the password with 277 queries.
3 Correct 1 ms 208 KB Guessed the password with 49 queries.
4 Correct 3 ms 208 KB Guessed the password with 133 queries.
5 Correct 3 ms 208 KB Guessed the password with 169 queries.
6 Correct 5 ms 208 KB Guessed the password with 293 queries.
7 Correct 159 ms 344 KB Guessed the password with 9608 queries.
8 Correct 258 ms 456 KB Guessed the password with 17345 queries.
9 Correct 348 ms 444 KB Guessed the password with 21757 queries.
10 Correct 573 ms 584 KB Guessed the password with 36498 queries.
11 Incorrect 788 ms 456 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 2 ms 208 KB Guessed the password with 121 queries.
2 Correct 6 ms 208 KB Guessed the password with 277 queries.
3 Correct 1 ms 208 KB Guessed the password with 49 queries.
4 Correct 3 ms 208 KB Guessed the password with 133 queries.
5 Correct 3 ms 208 KB Guessed the password with 169 queries.
6 Correct 5 ms 208 KB Guessed the password with 293 queries.
7 Correct 159 ms 344 KB Guessed the password with 9608 queries.
8 Correct 258 ms 456 KB Guessed the password with 17345 queries.
9 Correct 348 ms 444 KB Guessed the password with 21757 queries.
10 Correct 573 ms 584 KB Guessed the password with 36498 queries.
11 Incorrect 788 ms 456 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -