oj.uz

Submission #918695

# Submission time Handle Problem Language Result Execution time Memory
918695 2024-01-30T09:23:43 Z nasir_bashirov Password (RMI18_password) C++17
80 / 100
 325 ms 4752 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);

#define pci pair<char, int>

map<pair<pci, pci>, bool> memo;
map<char, int> cnt;

bool comp(pair<char, int> a, pair<char, int> b){
    if(a.first == b.first){
        return a.second < b.second;
    }
    if(memo.count({a, b}))    return memo[{a, b}];  
    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;
    }
    return memo[{a, b}] = (query(s) == (int)s.size());
}

string guess(int n, int s){
    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;
    }
    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 1 ms 436 KB Guessed the password with 83 queries.
2 Correct 1 ms 440 KB Guessed the password with 132 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 432 KB Guessed the password with 134 queries.
2 Correct 1 ms 436 KB Guessed the password with 248 queries.
3 Correct 0 ms 436 KB Guessed the password with 38 queries.
4 Correct 3 ms 436 KB Guessed the password with 519 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 1668 KB Guessed the password with 9309 queries.
2 Correct 64 ms 2568 KB Guessed the password with 11939 queries.
3 Correct 107 ms 2576 KB Guessed the password with 16746 queries.
4 Correct 143 ms 2748 KB Guessed the password with 21320 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 436 KB Guessed the password with 83 queries.
2 Correct 1 ms 440 KB Guessed the password with 132 queries.
3 Correct 1 ms 432 KB Guessed the password with 134 queries.
4 Correct 1 ms 436 KB Guessed the password with 248 queries.
5 Correct 0 ms 436 KB Guessed the password with 38 queries.
6 Correct 3 ms 436 KB Guessed the password with 519 queries.
7 Correct 52 ms 1668 KB Guessed the password with 9309 queries.
8 Correct 64 ms 2568 KB Guessed the password with 11939 queries.
9 Correct 107 ms 2576 KB Guessed the password with 16746 queries.
10 Correct 143 ms 2748 KB Guessed the password with 21320 queries.
11 Correct 216 ms 3940 KB Guessed the password with 32752 queries.
12 Correct 238 ms 3708 KB Guessed the password with 33481 queries.
13 Correct 236 ms 3648 KB Guessed the password with 36843 queries.
14 Correct 248 ms 3580 KB Guessed the password with 35195 queries.
15 Correct 254 ms 3968 KB Guessed the password with 39335 queries.
16 Correct 282 ms 3756 KB Guessed the password with 39615 queries.
17 Correct 278 ms 3984 KB Guessed the password with 38586 queries.
18 Correct 270 ms 4140 KB Guessed the password with 36513 queries.
19 Correct 273 ms 4332 KB Guessed the password with 39413 queries.
20 Correct 325 ms 4316 KB Guessed the password with 41659 queries.
21 Correct 222 ms 3508 KB Guessed the password with 32839 queries.
22 Correct 206 ms 3448 KB Guessed the password with 30615 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 436 KB Guessed the password with 83 queries.
2 Correct 1 ms 440 KB Guessed the password with 132 queries.
3 Correct 1 ms 432 KB Guessed the password with 134 queries.
4 Correct 1 ms 436 KB Guessed the password with 248 queries.
5 Correct 0 ms 436 KB Guessed the password with 38 queries.
6 Correct 3 ms 436 KB Guessed the password with 519 queries.
7 Correct 52 ms 1668 KB Guessed the password with 9309 queries.
8 Correct 64 ms 2568 KB Guessed the password with 11939 queries.
9 Correct 107 ms 2576 KB Guessed the password with 16746 queries.
10 Correct 143 ms 2748 KB Guessed the password with 21320 queries.
11 Correct 216 ms 3940 KB Guessed the password with 32752 queries.
12 Correct 238 ms 3708 KB Guessed the password with 33481 queries.
13 Correct 236 ms 3648 KB Guessed the password with 36843 queries.
14 Correct 248 ms 3580 KB Guessed the password with 35195 queries.
15 Correct 254 ms 3968 KB Guessed the password with 39335 queries.
16 Correct 282 ms 3756 KB Guessed the password with 39615 queries.
17 Correct 278 ms 3984 KB Guessed the password with 38586 queries.
18 Correct 270 ms 4140 KB Guessed the password with 36513 queries.
19 Correct 273 ms 4332 KB Guessed the password with 39413 queries.
20 Correct 325 ms 4316 KB Guessed the password with 41659 queries.
21 Correct 222 ms 3508 KB Guessed the password with 32839 queries.
22 Correct 206 ms 3448 KB Guessed the password with 30615 queries.
23 Incorrect 324 ms 4752 KB Could not guess the password with 50000 queries.
24 Halted 0 ms 0 KB -