oj.uz

Submission #722076

# Submission time Handle Problem Language Result Execution time Memory
722076 2023-04-11T11:38:06 Z nguyentunglam Password (RMI18_password) C++17
80 / 100
 1180 ms 588 KB 
#include<bits/stdc++.h>
using namespace std;

const int N = 5010;
int cnt[N];
char a[N], b[N];

int query(string q);

string guess(int n, int s) {
    vector<pair<int, char> > lst;
    for(int j = 0; j < s; j++) {
        char c = j + 'a';
        string ask;
        for(int i = 1; i <= n; i++) ask.push_back(c);
        int tmp = query(ask);
        if (tmp) lst.emplace_back(tmp, c);
    }
    sort(lst.begin(), lst.end());

    int m; char c;
    tie(m, c) = lst[0];
    for(int i = 1; i <= m; i++) a[i] = c;
    lst.erase(lst.begin());

    for(auto &it : lst) {
        int num; char c;
        tie(num, c) = it;
        for(int i = 1; i <= m; i++) {
            string ask;
            for(int j = 1; j <= i; j++) ask.push_back(a[j]);
            cnt[i] = 0;
            while (num > 0) {
                ask.push_back(c);
                string tmp;
                for(int j = i + 1; j <= m; j++) tmp.push_back(a[j]);
                if (query(ask + tmp) > m + cnt[i]) cnt[i]++, num--;
                else break;
            }
        }
        cnt[0] = num;
        int m2 = 0;
        for(int i = 0; i <= m; i++) {
            if (i) b[++m2] = a[i];
            while (cnt[i]--) b[++m2] = c;
        }
        for(int i = 1; i <= m2; i++) a[i] = b[i];
        m = m2;
    }
    string ret;
    for(int i = 1; i <= m; i++) ret.push_back(a[i]);
    return ret;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 77 queries.
2 Correct 2 ms 304 KB Guessed the password with 194 queries.

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 308 KB Guessed the password with 3131 queries.
2 Correct 127 ms 320 KB Guessed the password with 9154 queries.
3 Correct 74 ms 320 KB Guessed the password with 5185 queries.
4 Correct 201 ms 444 KB Guessed the password with 13854 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 77 queries.
2 Correct 2 ms 304 KB Guessed the password with 194 queries.
3 Correct 1 ms 208 KB Guessed the password with 48 queries.
4 Correct 1 ms 208 KB Guessed the password with 92 queries.
5 Correct 1 ms 208 KB Guessed the password with 18 queries.
6 Correct 2 ms 308 KB Guessed the password with 178 queries.
7 Correct 42 ms 308 KB Guessed the password with 3131 queries.
8 Correct 127 ms 320 KB Guessed the password with 9154 queries.
9 Correct 74 ms 320 KB Guessed the password with 5185 queries.
10 Correct 201 ms 444 KB Guessed the password with 13854 queries.
11 Correct 127 ms 344 KB Guessed the password with 9338 queries.
12 Correct 161 ms 348 KB Guessed the password with 9391 queries.
13 Correct 350 ms 348 KB Guessed the password with 17800 queries.
14 Correct 315 ms 352 KB Guessed the password with 18177 queries.
15 Correct 290 ms 472 KB Guessed the password with 14444 queries.
16 Correct 241 ms 340 KB Guessed the password with 14299 queries.
17 Correct 244 ms 588 KB Guessed the password with 12164 queries.
18 Correct 181 ms 340 KB Guessed the password with 12237 queries.
19 Correct 205 ms 344 KB Guessed the password with 10925 queries.
20 Correct 198 ms 464 KB Guessed the password with 11172 queries.
21 Correct 318 ms 352 KB Guessed the password with 15078 queries.
22 Correct 305 ms 344 KB Guessed the password with 15089 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 77 queries.
2 Correct 2 ms 304 KB Guessed the password with 194 queries.
3 Correct 1 ms 208 KB Guessed the password with 48 queries.
4 Correct 1 ms 208 KB Guessed the password with 92 queries.
5 Correct 1 ms 208 KB Guessed the password with 18 queries.
6 Correct 2 ms 308 KB Guessed the password with 178 queries.
7 Correct 42 ms 308 KB Guessed the password with 3131 queries.
8 Correct 127 ms 320 KB Guessed the password with 9154 queries.
9 Correct 74 ms 320 KB Guessed the password with 5185 queries.
10 Correct 201 ms 444 KB Guessed the password with 13854 queries.
11 Correct 127 ms 344 KB Guessed the password with 9338 queries.
12 Correct 161 ms 348 KB Guessed the password with 9391 queries.
13 Correct 350 ms 348 KB Guessed the password with 17800 queries.
14 Correct 315 ms 352 KB Guessed the password with 18177 queries.
15 Correct 290 ms 472 KB Guessed the password with 14444 queries.
16 Correct 241 ms 340 KB Guessed the password with 14299 queries.
17 Correct 244 ms 588 KB Guessed the password with 12164 queries.
18 Correct 181 ms 340 KB Guessed the password with 12237 queries.
19 Correct 205 ms 344 KB Guessed the password with 10925 queries.
20 Correct 198 ms 464 KB Guessed the password with 11172 queries.
21 Correct 318 ms 352 KB Guessed the password with 15078 queries.
22 Correct 305 ms 344 KB Guessed the password with 15089 queries.
23 Incorrect 1180 ms 448 KB Could not guess the password with 50000 queries.
24 Halted 0 ms 0 KB -