oj.uz

Submission #666345

# Submission time Handle Problem Language Result Execution time Memory
666345 2022-11-28T08:45:18 Z Nursik Password (RMI18_password) C++14
100 / 100
 326 ms 708 KB 
#include <stdio.h>
 
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
 
using namespace std;
 
#define ll long long
#define pb push_back
#define mp make_pair

int query(string str);
pair<int, string> combine(string a, string b){
    string ans = "";
    int i = 0, j = 0;
    int n = (int)a.size(), m = (int)b.size();
    int cl = m;
    while (i < n && j < m){
        string cur = "";
        cur += ans;
        cur += a[i];
        for (int pos = j; pos < m; ++pos){
            cur += b[pos];
        }
        int kek = query(cur);
        if (cl + 1 == kek){
            ans += a[i++];
            cl += 1;
        }
        else{
            ans += b[j++];
        }
    }
    for (int pos = j; pos < m; ++pos){
        ans += b[pos];
    }
    for (int pos = i; pos < n; ++pos){
        ans += a[pos];
    }
    return mp(n + m, ans);
}
string guess(int n, int s){
    multiset<pair<int, string>> setik;
    for (int i = 0; i < s; ++i){
        string q = "";
        char ch = 'a';
        ch += i;
        for (int j = 0; j < n; ++j){
            q += ch;
        }
        int kek = query(q);
        string w = "";
        for (int j = 1; j <= kek; ++j){
            w += ch;
        }
        if (kek){
            setik.insert(mp(kek, w));
        }
    }
    while (setik.size() != 1){
        pair<int, string> cur = *setik.begin();
        setik.erase(setik.find(cur));
        pair<int, string> cur2 = *setik.begin();
        setik.erase(setik.find(cur2));
        pair<int, string> ncur = combine(cur.second, cur2.second);
        setik.insert(ncur);
    }
    pair<int, string> ans = *setik.begin();
    return ans.second;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 58 queries.
2 Correct 1 ms 208 KB Guessed the password with 103 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 49 queries.
2 Correct 1 ms 208 KB Guessed the password with 90 queries.
3 Correct 2 ms 208 KB Guessed the password with 92 queries.
4 Correct 2 ms 208 KB Guessed the password with 178 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 328 KB Guessed the password with 2750 queries.
2 Correct 50 ms 340 KB Guessed the password with 5070 queries.
3 Correct 54 ms 328 KB Guessed the password with 4588 queries.
4 Correct 102 ms 440 KB Guessed the password with 8084 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 58 queries.
2 Correct 1 ms 208 KB Guessed the password with 103 queries.
3 Correct 1 ms 208 KB Guessed the password with 49 queries.
4 Correct 1 ms 208 KB Guessed the password with 90 queries.
5 Correct 2 ms 208 KB Guessed the password with 92 queries.
6 Correct 2 ms 208 KB Guessed the password with 178 queries.
7 Correct 33 ms 328 KB Guessed the password with 2750 queries.
8 Correct 50 ms 340 KB Guessed the password with 5070 queries.
9 Correct 54 ms 328 KB Guessed the password with 4588 queries.
10 Correct 102 ms 440 KB Guessed the password with 8084 queries.
11 Correct 63 ms 344 KB Guessed the password with 8154 queries.
12 Correct 95 ms 352 KB Guessed the password with 8162 queries.
13 Correct 140 ms 356 KB Guessed the password with 11502 queries.
14 Correct 186 ms 364 KB Guessed the password with 11602 queries.
15 Correct 143 ms 352 KB Guessed the password with 10880 queries.
16 Correct 141 ms 352 KB Guessed the password with 10861 queries.
17 Correct 125 ms 360 KB Guessed the password with 10211 queries.
18 Correct 145 ms 472 KB Guessed the password with 10247 queries.
19 Correct 129 ms 460 KB Guessed the password with 9688 queries.
20 Correct 116 ms 356 KB Guessed the password with 9775 queries.
21 Correct 160 ms 484 KB Guessed the password with 11639 queries.
22 Correct 151 ms 472 KB Guessed the password with 11710 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 58 queries.
2 Correct 1 ms 208 KB Guessed the password with 103 queries.
3 Correct 1 ms 208 KB Guessed the password with 49 queries.
4 Correct 1 ms 208 KB Guessed the password with 90 queries.
5 Correct 2 ms 208 KB Guessed the password with 92 queries.
6 Correct 2 ms 208 KB Guessed the password with 178 queries.
7 Correct 33 ms 328 KB Guessed the password with 2750 queries.
8 Correct 50 ms 340 KB Guessed the password with 5070 queries.
9 Correct 54 ms 328 KB Guessed the password with 4588 queries.
10 Correct 102 ms 440 KB Guessed the password with 8084 queries.
11 Correct 63 ms 344 KB Guessed the password with 8154 queries.
12 Correct 95 ms 352 KB Guessed the password with 8162 queries.
13 Correct 140 ms 356 KB Guessed the password with 11502 queries.
14 Correct 186 ms 364 KB Guessed the password with 11602 queries.
15 Correct 143 ms 352 KB Guessed the password with 10880 queries.
16 Correct 141 ms 352 KB Guessed the password with 10861 queries.
17 Correct 125 ms 360 KB Guessed the password with 10211 queries.
18 Correct 145 ms 472 KB Guessed the password with 10247 queries.
19 Correct 129 ms 460 KB Guessed the password with 9688 queries.
20 Correct 116 ms 356 KB Guessed the password with 9775 queries.
21 Correct 160 ms 484 KB Guessed the password with 11639 queries.
22 Correct 151 ms 472 KB Guessed the password with 11710 queries.
23 Correct 250 ms 504 KB Guessed the password with 23704 queries.
24 Correct 293 ms 444 KB Guessed the password with 20965 queries.
25 Correct 296 ms 596 KB Guessed the password with 23669 queries.
26 Correct 244 ms 708 KB Guessed the password with 19100 queries.
27 Correct 326 ms 512 KB Guessed the password with 23703 queries.
28 Correct 218 ms 500 KB Guessed the password with 16821 queries.
29 Correct 303 ms 576 KB Guessed the password with 23707 queries.
30 Correct 209 ms 372 KB Guessed the password with 14391 queries.