oj.uz

Submission #918719

# Submission time Handle Problem Language Result Execution time Memory
918719 2024-01-30T09:58:50 Z vjudge1 Password (RMI18_password) C++17
100 / 100
 301 ms 13976 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 75 queries.
2 Correct 3 ms 12632 KB Guessed the password with 123 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Guessed the password with 56 queries.
2 Correct 1 ms 2504 KB Guessed the password with 110 queries.
3 Correct 1 ms 2508 KB Guessed the password with 29 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 20 ms 6676 KB Guessed the password with 3232 queries.
2 Correct 28 ms 8732 KB Guessed the password with 3834 queries.
3 Correct 45 ms 10792 KB Guessed the password with 6650 queries.
4 Correct 84 ms 10812 KB Guessed the password with 9434 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Guessed the password with 75 queries.
2 Correct 3 ms 12632 KB Guessed the password with 123 queries.
3 Correct 1 ms 2392 KB Guessed the password with 56 queries.
4 Correct 1 ms 2504 KB Guessed the password with 110 queries.
5 Correct 1 ms 2508 KB Guessed the password with 29 queries.
6 Correct 2 ms 2512 KB Guessed the password with 238 queries.
7 Correct 20 ms 6676 KB Guessed the password with 3232 queries.
8 Correct 28 ms 8732 KB Guessed the password with 3834 queries.
9 Correct 45 ms 10792 KB Guessed the password with 6650 queries.
10 Correct 84 ms 10812 KB Guessed the password with 9434 queries.
11 Correct 105 ms 13976 KB Guessed the password with 11498 queries.
12 Correct 103 ms 13664 KB Guessed the password with 11607 queries.
13 Correct 108 ms 13756 KB Guessed the password with 13883 queries.
14 Correct 108 ms 13532 KB Guessed the password with 13850 queries.
15 Correct 137 ms 13800 KB Guessed the password with 15268 queries.
16 Correct 130 ms 13576 KB Guessed the password with 14939 queries.
17 Correct 117 ms 13588 KB Guessed the password with 13193 queries.
18 Correct 123 ms 13596 KB Guessed the password with 12908 queries.
19 Correct 119 ms 13616 KB Guessed the password with 13614 queries.
20 Correct 144 ms 13616 KB Guessed the password with 13941 queries.
21 Correct 79 ms 13628 KB Guessed the password with 8484 queries.
22 Correct 75 ms 13632 KB Guessed the password with 8120 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Guessed the password with 75 queries.
2 Correct 3 ms 12632 KB Guessed the password with 123 queries.
3 Correct 1 ms 2392 KB Guessed the password with 56 queries.
4 Correct 1 ms 2504 KB Guessed the password with 110 queries.
5 Correct 1 ms 2508 KB Guessed the password with 29 queries.
6 Correct 2 ms 2512 KB Guessed the password with 238 queries.
7 Correct 20 ms 6676 KB Guessed the password with 3232 queries.
8 Correct 28 ms 8732 KB Guessed the password with 3834 queries.
9 Correct 45 ms 10792 KB Guessed the password with 6650 queries.
10 Correct 84 ms 10812 KB Guessed the password with 9434 queries.
11 Correct 105 ms 13976 KB Guessed the password with 11498 queries.
12 Correct 103 ms 13664 KB Guessed the password with 11607 queries.
13 Correct 108 ms 13756 KB Guessed the password with 13883 queries.
14 Correct 108 ms 13532 KB Guessed the password with 13850 queries.
15 Correct 137 ms 13800 KB Guessed the password with 15268 queries.
16 Correct 130 ms 13576 KB Guessed the password with 14939 queries.
17 Correct 117 ms 13588 KB Guessed the password with 13193 queries.
18 Correct 123 ms 13596 KB Guessed the password with 12908 queries.
19 Correct 119 ms 13616 KB Guessed the password with 13614 queries.
20 Correct 144 ms 13616 KB Guessed the password with 13941 queries.
21 Correct 79 ms 13628 KB Guessed the password with 8484 queries.
22 Correct 75 ms 13632 KB Guessed the password with 8120 queries.
23 Correct 164 ms 13764 KB Guessed the password with 16500 queries.
24 Correct 140 ms 13912 KB Guessed the password with 14154 queries.
25 Correct 247 ms 13764 KB Guessed the password with 27598 queries.
26 Correct 221 ms 13772 KB Guessed the password with 22489 queries.
27 Correct 296 ms 13768 KB Guessed the password with 30704 queries.
28 Correct 226 ms 13940 KB Guessed the password with 22617 queries.
29 Correct 301 ms 13884 KB Guessed the password with 33270 queries.
30 Correct 235 ms 13772 KB Guessed the password with 20609 queries.