Submission #394303

#	Time	Username	Problem	Language	Result	Execution time	Memory
394303		jsannemo	Password (RMI18_password)	C++14	100 / 100	544 ms	700 KiB

password

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int query(string q);

string guess(int N, int S) {
	string res;
	{
		string q(N, 'a');
		res = string(query(q), 'a');
	}
	for (int i = 1; i < S; ++i) {
		int included = 0;
		int at = sz(res);
		while (true) {
			int lo = -1;
			int hi = at + 1;
			while (hi - lo > 1) {
				int mid = (lo + hi + 1) / 2;
				string q = res.substr(0, mid) + string(included + 1, 'a' + i);
				if (query(q) == sz(q)) {
					lo = mid;
				} else {
					hi = mid;
				}
			}
			if (lo == -1) break;
			res.insert(res.begin() + lo, 'a' + i);
			at = hi;
			++included;
		}
	}
	return res;
}

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