oj.uz

Submission #918778

# Submission time Handle Problem Language Result Execution time Memory
918778 2024-01-30T12:31:33 Z vjudge1 Password (RMI18_password) C++17
100 / 100
 405 ms 14436 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
#include <bits/stdc++.h>
using namespace std;
 
#define db long double
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
// #define endl '\n'
#define all(x) x.begin(), x.end()
#define fastio\
    ios_base::sync_with_stdio(0);\
    cin.tie(0);\
    cout.tie(0)\
 
int query(string str);
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
#define pci pair<char, int>
 
int memo[26][26][5001];
map<char, int> cnt;
int N;
bool comp(pair<char, int> a, pair<char, int> b){
    if(a.first == b.first){
        return a.second < b.second;
    }
    for(int i=a.second; i <= N; i++){
        if(memo[a.first-'a'][b.first-'a'][i]<=b.second){
            return true;
        }
    }
    for(int i=b.second; i<=N; i++){
        if(memo[b.first-'a'][a.first-'a'][i]<=a.second){
            return false;
        }
    }
    string s = "";
    for(int i = 1; i <= a.second; i++){
        s += a.first;
    }
    for(int i = 1; i <= cnt[b.first] - b.second + 1; i++){
        s += b.first;
    }
    bool ok=(query(s)==(int)s.size());
    if(ok){
        memo[a.first - 'a'][b.first - 'a'][a.second]=min(memo[a.first - 'a'][b.first - 'a'][a.second],b.second);
    }
    else{
        memo[b.first - 'a'][a.first - 'a'][b.second]=min(memo[b.first - 'a'][a.first - 'a'][b.second],a.second);
    }
    return ok;
}
 
string guess(int n, int s){
    N=n;
    for(int i = 0;i < s ;i++){
        for(int j = 0;j < s; j++){
            for(int z =1 ;z <= n; z++){
                memo[i][j][z] = n+1;
            }
        }
    }
    vector<pci> v;
    for(char c = 'a'; c <= char('a' + s - 1);  c++){
        string s1 = "";
        for(int j = 1; j <= n; j++){
            s1 += c;
        }
        cnt[c] = query(s1);
        for(int j = 1; j <= cnt[c]; j++){
            v.push_back({c, j});
        }
        // cout << c << " : " << cnt[c] << endl;
    }
    //shuffle(all(v), rng);
    reverse(all(v));
    sort(all(v), comp);
    string res = "";
    for(auto i : v){
        res += i.first;
    }
    return res;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Guessed the password with 84 queries.
2 Correct 3 ms 12632 KB Guessed the password with 120 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Guessed the password with 63 queries.
2 Correct 1 ms 2504 KB Guessed the password with 126 queries.
3 Correct 1 ms 2500 KB Guessed the password with 20 queries.
4 Correct 2 ms 2508 KB Guessed the password with 259 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6676 KB Guessed the password with 4751 queries.
2 Correct 40 ms 8732 KB Guessed the password with 6211 queries.
3 Correct 65 ms 10796 KB Guessed the password with 9970 queries.
4 Correct 88 ms 10812 KB Guessed the password with 13250 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Guessed the password with 84 queries.
2 Correct 3 ms 12632 KB Guessed the password with 120 queries.
3 Correct 1 ms 2392 KB Guessed the password with 63 queries.
4 Correct 1 ms 2504 KB Guessed the password with 126 queries.
5 Correct 1 ms 2500 KB Guessed the password with 20 queries.
6 Correct 2 ms 2508 KB Guessed the password with 259 queries.
7 Correct 28 ms 6676 KB Guessed the password with 4751 queries.
8 Correct 40 ms 8732 KB Guessed the password with 6211 queries.
9 Correct 65 ms 10796 KB Guessed the password with 9970 queries.
10 Correct 88 ms 10812 KB Guessed the password with 13250 queries.
11 Correct 148 ms 13500 KB Guessed the password with 18761 queries.
12 Correct 135 ms 13492 KB Guessed the password with 17872 queries.
13 Correct 149 ms 13536 KB Guessed the password with 20006 queries.
14 Correct 138 ms 13536 KB Guessed the password with 20117 queries.
15 Correct 167 ms 13804 KB Guessed the password with 22593 queries.
16 Correct 180 ms 13572 KB Guessed the password with 22235 queries.
17 Correct 173 ms 13588 KB Guessed the password with 21088 queries.
18 Correct 156 ms 13592 KB Guessed the password with 19823 queries.
19 Correct 171 ms 13616 KB Guessed the password with 21191 queries.
20 Correct 188 ms 13616 KB Guessed the password with 22021 queries.
21 Correct 110 ms 13624 KB Guessed the password with 14744 queries.
22 Correct 122 ms 13624 KB Guessed the password with 13636 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Guessed the password with 84 queries.
2 Correct 3 ms 12632 KB Guessed the password with 120 queries.
3 Correct 1 ms 2392 KB Guessed the password with 63 queries.
4 Correct 1 ms 2504 KB Guessed the password with 126 queries.
5 Correct 1 ms 2500 KB Guessed the password with 20 queries.
6 Correct 2 ms 2508 KB Guessed the password with 259 queries.
7 Correct 28 ms 6676 KB Guessed the password with 4751 queries.
8 Correct 40 ms 8732 KB Guessed the password with 6211 queries.
9 Correct 65 ms 10796 KB Guessed the password with 9970 queries.
10 Correct 88 ms 10812 KB Guessed the password with 13250 queries.
11 Correct 148 ms 13500 KB Guessed the password with 18761 queries.
12 Correct 135 ms 13492 KB Guessed the password with 17872 queries.
13 Correct 149 ms 13536 KB Guessed the password with 20006 queries.
14 Correct 138 ms 13536 KB Guessed the password with 20117 queries.
15 Correct 167 ms 13804 KB Guessed the password with 22593 queries.
16 Correct 180 ms 13572 KB Guessed the password with 22235 queries.
17 Correct 173 ms 13588 KB Guessed the password with 21088 queries.
18 Correct 156 ms 13592 KB Guessed the password with 19823 queries.
19 Correct 171 ms 13616 KB Guessed the password with 21191 queries.
20 Correct 188 ms 13616 KB Guessed the password with 22021 queries.
21 Correct 110 ms 13624 KB Guessed the password with 14744 queries.
22 Correct 122 ms 13624 KB Guessed the password with 13636 queries.
23 Correct 238 ms 13772 KB Guessed the password with 26695 queries.
24 Correct 216 ms 13848 KB Guessed the password with 24195 queries.
25 Correct 335 ms 13860 KB Guessed the password with 39001 queries.
26 Correct 308 ms 14436 KB Guessed the password with 35118 queries.
27 Correct 354 ms 13764 KB Guessed the password with 42376 queries.
28 Correct 329 ms 13868 KB Guessed the password with 35246 queries.
29 Correct 405 ms 13848 KB Guessed the password with 42770 queries.
30 Correct 344 ms 13768 KB Guessed the password with 34182 queries.