Submission #723242

#	Time	Username	Problem	Language	Result	Execution time	Memory
723242		tvladm2009	Password (RMI18_password)	C++17	100 / 100	333 ms	668 KiB

password

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int query(string s);

int N;

string solve(int l, int r) {
    int mid = (l + r) / 2;
    if (l == r) {
        string qry = "";
        for (int j = 1; j <= N; j++) {
            qry += char('a' + l);
        }
        int resp = query(qry);
        string answer = "";
        for (int j = 1; j <= resp; j++) {
            answer += char('a' + l);
        }
        return answer;
    }
    string a = solve(l, mid);
    string b = solve(mid + 1, r);
    string answer = "";
    int posA = 0, posB = 0;
    while (posA < (int) a.size()) {
        while (true) {
            string qry = answer;
            qry += a[posA];
            for (int j = posB; j < (int) b.size(); j++) {
                qry += b[j];
            }
            int resp = query(qry);
            if (resp == (int) b.size() + posA + 1) {
                answer += a[posA];
                break;
            }
            answer += b[posB];
            posB++;
        }
        posA++;
    }
    for (int i = posB; i < (int) b.size(); i++) {
        answer += b[i];
    }
    return answer;
}

string guess(int _N, int S) {
    N = _N;
    string answer = solve(0, S - 1);
    return answer;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 30 / 30
• Subtask 5: 20 / 20