oj.uz

Submission #899820

# Submission time Handle Problem Language Result Execution time Memory
899820 2024-01-07T05:57:33 Z Cookie Password (RMI18_password) C++14
100 / 100
 171 ms 1784 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
int query(string s);
bool cmp(string a, string b){
    return(sz(a) > sz(b));
}
vt<string>v;
string guess(int n, int s){
    for(int i = 0; i < s; i++){
        string s = "";
        while(1){
            s += (i + 'a');
            if(query(s) != sz(s)){
                s.pop_back(); break;
            }
        }
        if(s != "")v.pb(s);
    }
    //for(auto i: v)cout << i << " ";
    while(sz(v) > 1){
        sort(ALL(v), cmp);
        string s1 = v.back(), s2 = v[sz(v) - 2];
        int l1 = 0, l2 = 0;
        string s3 = "";
        while(l1 < sz(s1) || l2 < sz(s2)){
            if(l1 == sz(s1))s3 += s2[l2++];
            else if(l2 == sz(s2))s3 += s1[l1++];
            else{
                string s4 = s3 + s1[l1];
                for(int i = l2; i < sz(s2); i++)s4 += s2[i];

                if(query(s4) == sz(s4)){
                    s3 += s1[l1++];
                }else{
                    s3 += s2[l2++];
                }
            }
        }

        v.pop_back(); v.pop_back(); v.pb(s3);
    }
    return(v[0]);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 72 queries.
2 Correct 1 ms 432 KB Guessed the password with 127 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 99 queries.
2 Correct 1 ms 344 KB Guessed the password with 160 queries.
3 Correct 1 ms 344 KB Guessed the password with 182 queries.
4 Correct 1 ms 436 KB Guessed the password with 278 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1196 KB Guessed the password with 3750 queries.
2 Correct 48 ms 696 KB Guessed the password with 6370 queries.
3 Correct 34 ms 696 KB Guessed the password with 6187 queries.
4 Correct 57 ms 1460 KB Guessed the password with 10084 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 72 queries.
2 Correct 1 ms 432 KB Guessed the password with 127 queries.
3 Correct 1 ms 344 KB Guessed the password with 99 queries.
4 Correct 1 ms 344 KB Guessed the password with 160 queries.
5 Correct 1 ms 344 KB Guessed the password with 182 queries.
6 Correct 1 ms 436 KB Guessed the password with 278 queries.
7 Correct 17 ms 1196 KB Guessed the password with 3750 queries.
8 Correct 48 ms 696 KB Guessed the password with 6370 queries.
9 Correct 34 ms 696 KB Guessed the password with 6187 queries.
10 Correct 57 ms 1460 KB Guessed the password with 10084 queries.
11 Correct 57 ms 1236 KB Guessed the password with 10958 queries.
12 Correct 63 ms 732 KB Guessed the password with 10960 queries.
13 Correct 82 ms 744 KB Guessed the password with 14502 queries.
14 Correct 84 ms 992 KB Guessed the password with 14602 queries.
15 Correct 69 ms 1204 KB Guessed the password with 14082 queries.
16 Correct 86 ms 956 KB Guessed the password with 14059 queries.
17 Correct 71 ms 1244 KB Guessed the password with 13509 queries.
18 Correct 87 ms 1196 KB Guessed the password with 13544 queries.
19 Correct 72 ms 1492 KB Guessed the password with 13085 queries.
20 Correct 72 ms 980 KB Guessed the password with 13178 queries.
21 Correct 86 ms 948 KB Guessed the password with 15139 queries.
22 Correct 77 ms 1212 KB Guessed the password with 15208 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 72 queries.
2 Correct 1 ms 432 KB Guessed the password with 127 queries.
3 Correct 1 ms 344 KB Guessed the password with 99 queries.
4 Correct 1 ms 344 KB Guessed the password with 160 queries.
5 Correct 1 ms 344 KB Guessed the password with 182 queries.
6 Correct 1 ms 436 KB Guessed the password with 278 queries.
7 Correct 17 ms 1196 KB Guessed the password with 3750 queries.
8 Correct 48 ms 696 KB Guessed the password with 6370 queries.
9 Correct 34 ms 696 KB Guessed the password with 6187 queries.
10 Correct 57 ms 1460 KB Guessed the password with 10084 queries.
11 Correct 57 ms 1236 KB Guessed the password with 10958 queries.
12 Correct 63 ms 732 KB Guessed the password with 10960 queries.
13 Correct 82 ms 744 KB Guessed the password with 14502 queries.
14 Correct 84 ms 992 KB Guessed the password with 14602 queries.
15 Correct 69 ms 1204 KB Guessed the password with 14082 queries.
16 Correct 86 ms 956 KB Guessed the password with 14059 queries.
17 Correct 71 ms 1244 KB Guessed the password with 13509 queries.
18 Correct 87 ms 1196 KB Guessed the password with 13544 queries.
19 Correct 72 ms 1492 KB Guessed the password with 13085 queries.
20 Correct 72 ms 980 KB Guessed the password with 13178 queries.
21 Correct 86 ms 948 KB Guessed the password with 15139 queries.
22 Correct 77 ms 1212 KB Guessed the password with 15208 queries.
23 Correct 165 ms 1432 KB Guessed the password with 28647 queries.
24 Correct 164 ms 1784 KB Guessed the password with 25965 queries.
25 Correct 171 ms 1392 KB Guessed the password with 28671 queries.
26 Correct 142 ms 1356 KB Guessed the password with 24099 queries.
27 Correct 167 ms 1592 KB Guessed the password with 28699 queries.
28 Correct 131 ms 1712 KB Guessed the password with 21822 queries.
29 Correct 169 ms 1340 KB Guessed the password with 28707 queries.
30 Correct 119 ms 1544 KB Guessed the password with 19392 queries.