oj.uz

답안 #918699

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
918699 2024-01-30T09:25:13 Z nasir_bashirov Password (RMI18_password) C++17
80 / 100
 353 ms 4676 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>

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;
    }
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 444 KB Guessed the password with 85 queries.
2 Correct 1 ms 436 KB Guessed the password with 123 queries.

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 444 KB Guessed the password with 129 queries.
2 Correct 1 ms 440 KB Guessed the password with 198 queries.
3 Correct 1 ms 436 KB Guessed the password with 70 queries.
4 Correct 3 ms 696 KB Guessed the password with 461 queries.

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 1944 KB Guessed the password with 9104 queries.
2 Correct 75 ms 2512 KB Guessed the password with 11068 queries.
3 Correct 117 ms 2856 KB Guessed the password with 16093 queries.
4 Correct 124 ms 2656 KB Guessed the password with 20443 queries.

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 444 KB Guessed the password with 85 queries.
2 Correct 1 ms 436 KB Guessed the password with 123 queries.
3 Correct 1 ms 444 KB Guessed the password with 129 queries.
4 Correct 1 ms 440 KB Guessed the password with 198 queries.
5 Correct 1 ms 436 KB Guessed the password with 70 queries.
6 Correct 3 ms 696 KB Guessed the password with 461 queries.
7 Correct 55 ms 1944 KB Guessed the password with 9104 queries.
8 Correct 75 ms 2512 KB Guessed the password with 11068 queries.
9 Correct 117 ms 2856 KB Guessed the password with 16093 queries.
10 Correct 124 ms 2656 KB Guessed the password with 20443 queries.
11 Correct 255 ms 3256 KB Guessed the password with 29312 queries.
12 Correct 211 ms 3348 KB Guessed the password with 30082 queries.
13 Correct 214 ms 3464 KB Guessed the password with 31679 queries.
14 Correct 216 ms 3928 KB Guessed the password with 32043 queries.
15 Correct 268 ms 3932 KB Guessed the password with 36221 queries.
16 Correct 268 ms 3480 KB Guessed the password with 37369 queries.
17 Correct 261 ms 3948 KB Guessed the password with 35402 queries.
18 Correct 263 ms 3884 KB Guessed the password with 35298 queries.
19 Correct 282 ms 3424 KB Guessed the password with 36511 queries.
20 Correct 329 ms 3520 KB Guessed the password with 39922 queries.
21 Correct 179 ms 3072 KB Guessed the password with 24736 queries.
22 Correct 184 ms 3352 KB Guessed the password with 25391 queries.

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 444 KB Guessed the password with 85 queries.
2 Correct 1 ms 436 KB Guessed the password with 123 queries.
3 Correct 1 ms 444 KB Guessed the password with 129 queries.
4 Correct 1 ms 440 KB Guessed the password with 198 queries.
5 Correct 1 ms 436 KB Guessed the password with 70 queries.
6 Correct 3 ms 696 KB Guessed the password with 461 queries.
7 Correct 55 ms 1944 KB Guessed the password with 9104 queries.
8 Correct 75 ms 2512 KB Guessed the password with 11068 queries.
9 Correct 117 ms 2856 KB Guessed the password with 16093 queries.
10 Correct 124 ms 2656 KB Guessed the password with 20443 queries.
11 Correct 255 ms 3256 KB Guessed the password with 29312 queries.
12 Correct 211 ms 3348 KB Guessed the password with 30082 queries.
13 Correct 214 ms 3464 KB Guessed the password with 31679 queries.
14 Correct 216 ms 3928 KB Guessed the password with 32043 queries.
15 Correct 268 ms 3932 KB Guessed the password with 36221 queries.
16 Correct 268 ms 3480 KB Guessed the password with 37369 queries.
17 Correct 261 ms 3948 KB Guessed the password with 35402 queries.
18 Correct 263 ms 3884 KB Guessed the password with 35298 queries.
19 Correct 282 ms 3424 KB Guessed the password with 36511 queries.
20 Correct 329 ms 3520 KB Guessed the password with 39922 queries.
21 Correct 179 ms 3072 KB Guessed the password with 24736 queries.
22 Correct 184 ms 3352 KB Guessed the password with 25391 queries.
23 Correct 326 ms 4328 KB Guessed the password with 46322 queries.
24 Correct 353 ms 3988 KB Guessed the password with 44990 queries.
25 Incorrect 338 ms 4676 KB Could not guess the password with 50000 queries.
26 Halted 0 ms 0 KB -