oj.uz

답안 #464131

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
464131 2021-08-12T12:31:10 Z Mamedov Password (RMI18_password) C++17
50 / 100
 378 ms 448 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define ui unsigned int
#define pii pair<int, int>
#define piii pair<int, pii>
#define pb push_back
#define f first
#define s second
#define oo (1ll << 60)

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


int query(string str);


string guess(int n, int s) {
    string str;
    vector<int>countLetter(s);
    int maxLetter = 0;
    for(int i = 0; i < s; ++i) {
        str = "";
        for(int j = 0; j < n; ++j) {
            str += ('a' + i);
        }
        countLetter[i] = query(str);
        if(countLetter[i] > countLetter[maxLetter]) {
            maxLetter = i;
        }
    }
    str = "";
    for(int i = 0; i < countLetter[maxLetter]; ++i) {
        str += ('a' + maxLetter);
    }
    for(int i = 0; i < s; ++i) {
        if(i == maxLetter) continue;
        string add = "";
        for(int j = 0; j < countLetter[i]; ++j) {
            add += ('a' + i);
        }
        int len = str.length();
        vector<int>comesAfter(len + 2);
        comesAfter[0] = countLetter[i];
        comesAfter[len + 1] = 0;
        for(int j = 1; j <= len; ++j) {
            string ask = str.substr(0, j) + add;
            comesAfter[j] = query(ask) - j;
        }

        for(int j = 0; j <= len; ++j) {
            for(int k = comesAfter[j]; k > comesAfter[j + 1]; --k) {
                str.insert(str.begin() + j + countLetter[i] - k, 'a' + i);
            }
        }
    }
    return str;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Guessed the password with 29 queries.
2 Correct 1 ms 200 KB Guessed the password with 106 queries.
3 Correct 3 ms 200 KB Guessed the password with 169 queries.
4 Correct 2 ms 200 KB Guessed the password with 170 queries.

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 428 KB Guessed the password with 4706 queries.
2 Correct 117 ms 444 KB Guessed the password with 9550 queries.
3 Correct 111 ms 436 KB Guessed the password with 15206 queries.
4 Correct 146 ms 448 KB Guessed the password with 19286 queries.

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 200 KB Guessed the password with 121 queries.
2 Correct 4 ms 200 KB Guessed the password with 277 queries.
3 Correct 1 ms 200 KB Guessed the password with 29 queries.
4 Correct 1 ms 200 KB Guessed the password with 106 queries.
5 Correct 3 ms 200 KB Guessed the password with 169 queries.
6 Correct 2 ms 200 KB Guessed the password with 170 queries.
7 Correct 59 ms 428 KB Guessed the password with 4706 queries.
8 Correct 117 ms 444 KB Guessed the password with 9550 queries.
9 Correct 111 ms 436 KB Guessed the password with 15206 queries.
10 Correct 146 ms 448 KB Guessed the password with 19286 queries.
11 Incorrect 378 ms 360 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 200 KB Guessed the password with 121 queries.
2 Correct 4 ms 200 KB Guessed the password with 277 queries.
3 Correct 1 ms 200 KB Guessed the password with 29 queries.
4 Correct 1 ms 200 KB Guessed the password with 106 queries.
5 Correct 3 ms 200 KB Guessed the password with 169 queries.
6 Correct 2 ms 200 KB Guessed the password with 170 queries.
7 Correct 59 ms 428 KB Guessed the password with 4706 queries.
8 Correct 117 ms 444 KB Guessed the password with 9550 queries.
9 Correct 111 ms 436 KB Guessed the password with 15206 queries.
10 Correct 146 ms 448 KB Guessed the password with 19286 queries.
11 Incorrect 378 ms 360 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -