oj.uz

Submission #918704

# Submission time Handle Problem Language Result Execution time Memory
918704 2024-01-30T09:33:47 Z nasir_bashirov Password (RMI18_password) C++17
100 / 100
 363 ms 14772 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);
    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 79 queries.
2 Correct 3 ms 12632 KB Guessed the password with 128 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Guessed the password with 66 queries.
2 Correct 2 ms 2508 KB Guessed the password with 129 queries.
3 Correct 1 ms 2504 KB Guessed the password with 32 queries.
4 Correct 2 ms 2512 KB Guessed the password with 238 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6672 KB Guessed the password with 3398 queries.
2 Correct 27 ms 8988 KB Guessed the password with 3977 queries.
3 Correct 49 ms 11056 KB Guessed the password with 6666 queries.
4 Correct 77 ms 10808 KB Guessed the password with 9625 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Guessed the password with 79 queries.
2 Correct 3 ms 12632 KB Guessed the password with 128 queries.
3 Correct 1 ms 2392 KB Guessed the password with 66 queries.
4 Correct 2 ms 2508 KB Guessed the password with 129 queries.
5 Correct 1 ms 2504 KB Guessed the password with 32 queries.
6 Correct 2 ms 2512 KB Guessed the password with 238 queries.
7 Correct 24 ms 6672 KB Guessed the password with 3398 queries.
8 Correct 27 ms 8988 KB Guessed the password with 3977 queries.
9 Correct 49 ms 11056 KB Guessed the password with 6666 queries.
10 Correct 77 ms 10808 KB Guessed the password with 9625 queries.
11 Correct 98 ms 13500 KB Guessed the password with 11555 queries.
12 Correct 111 ms 13492 KB Guessed the password with 11560 queries.
13 Correct 116 ms 13656 KB Guessed the password with 13702 queries.
14 Correct 125 ms 14016 KB Guessed the password with 13814 queries.
15 Correct 134 ms 13576 KB Guessed the password with 15221 queries.
16 Correct 143 ms 14060 KB Guessed the password with 15257 queries.
17 Correct 121 ms 13592 KB Guessed the password with 13129 queries.
18 Correct 128 ms 13812 KB Guessed the password with 12928 queries.
19 Correct 129 ms 13652 KB Guessed the password with 13576 queries.
20 Correct 143 ms 13840 KB Guessed the password with 14059 queries.
21 Correct 86 ms 13656 KB Guessed the password with 8367 queries.
22 Correct 91 ms 13624 KB Guessed the password with 8296 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Guessed the password with 79 queries.
2 Correct 3 ms 12632 KB Guessed the password with 128 queries.
3 Correct 1 ms 2392 KB Guessed the password with 66 queries.
4 Correct 2 ms 2508 KB Guessed the password with 129 queries.
5 Correct 1 ms 2504 KB Guessed the password with 32 queries.
6 Correct 2 ms 2512 KB Guessed the password with 238 queries.
7 Correct 24 ms 6672 KB Guessed the password with 3398 queries.
8 Correct 27 ms 8988 KB Guessed the password with 3977 queries.
9 Correct 49 ms 11056 KB Guessed the password with 6666 queries.
10 Correct 77 ms 10808 KB Guessed the password with 9625 queries.
11 Correct 98 ms 13500 KB Guessed the password with 11555 queries.
12 Correct 111 ms 13492 KB Guessed the password with 11560 queries.
13 Correct 116 ms 13656 KB Guessed the password with 13702 queries.
14 Correct 125 ms 14016 KB Guessed the password with 13814 queries.
15 Correct 134 ms 13576 KB Guessed the password with 15221 queries.
16 Correct 143 ms 14060 KB Guessed the password with 15257 queries.
17 Correct 121 ms 13592 KB Guessed the password with 13129 queries.
18 Correct 128 ms 13812 KB Guessed the password with 12928 queries.
19 Correct 129 ms 13652 KB Guessed the password with 13576 queries.
20 Correct 143 ms 13840 KB Guessed the password with 14059 queries.
21 Correct 86 ms 13656 KB Guessed the password with 8367 queries.
22 Correct 91 ms 13624 KB Guessed the password with 8296 queries.
23 Correct 178 ms 13764 KB Guessed the password with 16509 queries.
24 Correct 143 ms 14376 KB Guessed the password with 14371 queries.
25 Correct 288 ms 13940 KB Guessed the password with 27522 queries.
26 Correct 246 ms 13764 KB Guessed the password with 22649 queries.
27 Correct 324 ms 14772 KB Guessed the password with 31001 queries.
28 Correct 273 ms 13956 KB Guessed the password with 22818 queries.
29 Correct 363 ms 13768 KB Guessed the password with 32814 queries.
30 Correct 237 ms 13900 KB Guessed the password with 21022 queries.