oj.uz

답안 #722070

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
722070 2023-04-11T11:31:02 Z nguyentunglam Password (RMI18_password) C++17
80 / 100
 1236 ms 476 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);
        lst.emplace_back(query(ask), 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 = 0; 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;
            }
        }
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 208 KB Guessed the password with 76 queries.
2 Correct 4 ms 208 KB Guessed the password with 187 queries.

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Guessed the password with 49 queries.
2 Correct 2 ms 208 KB Guessed the password with 94 queries.
3 Correct 1 ms 208 KB Guessed the password with 91 queries.
4 Correct 3 ms 208 KB Guessed the password with 180 queries.

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 332 KB Guessed the password with 3134 queries.
2 Correct 133 ms 336 KB Guessed the password with 9154 queries.
3 Correct 67 ms 452 KB Guessed the password with 5202 queries.
4 Correct 229 ms 336 KB Guessed the password with 13852 queries.

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 208 KB Guessed the password with 76 queries.
2 Correct 4 ms 208 KB Guessed the password with 187 queries.
3 Correct 1 ms 208 KB Guessed the password with 49 queries.
4 Correct 2 ms 208 KB Guessed the password with 94 queries.
5 Correct 1 ms 208 KB Guessed the password with 91 queries.
6 Correct 3 ms 208 KB Guessed the password with 180 queries.
7 Correct 30 ms 332 KB Guessed the password with 3134 queries.
8 Correct 133 ms 336 KB Guessed the password with 9154 queries.
9 Correct 67 ms 452 KB Guessed the password with 5202 queries.
10 Correct 229 ms 336 KB Guessed the password with 13852 queries.
11 Correct 178 ms 344 KB Guessed the password with 9348 queries.
12 Correct 157 ms 344 KB Guessed the password with 9405 queries.
13 Correct 311 ms 476 KB Guessed the password with 17814 queries.
14 Correct 275 ms 360 KB Guessed the password with 18090 queries.
15 Correct 279 ms 468 KB Guessed the password with 14446 queries.
16 Correct 286 ms 472 KB Guessed the password with 14325 queries.
17 Correct 228 ms 448 KB Guessed the password with 12188 queries.
18 Correct 205 ms 352 KB Guessed the password with 12217 queries.
19 Correct 196 ms 348 KB Guessed the password with 10934 queries.
20 Correct 211 ms 356 KB Guessed the password with 11170 queries.
21 Correct 297 ms 352 KB Guessed the password with 15076 queries.
22 Correct 258 ms 352 KB Guessed the password with 15000 queries.

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 208 KB Guessed the password with 76 queries.
2 Correct 4 ms 208 KB Guessed the password with 187 queries.
3 Correct 1 ms 208 KB Guessed the password with 49 queries.
4 Correct 2 ms 208 KB Guessed the password with 94 queries.
5 Correct 1 ms 208 KB Guessed the password with 91 queries.
6 Correct 3 ms 208 KB Guessed the password with 180 queries.
7 Correct 30 ms 332 KB Guessed the password with 3134 queries.
8 Correct 133 ms 336 KB Guessed the password with 9154 queries.
9 Correct 67 ms 452 KB Guessed the password with 5202 queries.
10 Correct 229 ms 336 KB Guessed the password with 13852 queries.
11 Correct 178 ms 344 KB Guessed the password with 9348 queries.
12 Correct 157 ms 344 KB Guessed the password with 9405 queries.
13 Correct 311 ms 476 KB Guessed the password with 17814 queries.
14 Correct 275 ms 360 KB Guessed the password with 18090 queries.
15 Correct 279 ms 468 KB Guessed the password with 14446 queries.
16 Correct 286 ms 472 KB Guessed the password with 14325 queries.
17 Correct 228 ms 448 KB Guessed the password with 12188 queries.
18 Correct 205 ms 352 KB Guessed the password with 12217 queries.
19 Correct 196 ms 348 KB Guessed the password with 10934 queries.
20 Correct 211 ms 356 KB Guessed the password with 11170 queries.
21 Correct 297 ms 352 KB Guessed the password with 15076 queries.
22 Correct 258 ms 352 KB Guessed the password with 15000 queries.
23 Incorrect 1236 ms 416 KB Could not guess the password with 50000 queries.
24 Halted 0 ms 0 KB -