Submission #394232

#	Time	Username	Problem	Language	Result	Execution time	Memory
394232		jsannemo	Password (RMI18_password)	C++14	80 / 100	659 ms	820 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);

vector<int> seen(26);
string alpha;

string go(const string& pre, int N, int S) {
	if (S < 0) return "";
	random_shuffle(alpha.begin(), alpha.begin() + S + 1);


	string q = pre + string(N - sz(pre), alpha[S]);
	int cnt = query(q) - seen[alpha[S] - 'a'] - sz(pre);

	string res;
	for (int i = cnt; i >= 0; --i) {
		string npre = pre;
		rep(j,0,i) npre.push_back(alpha[S]);

		if (i != cnt) {
			res.insert(res.begin(), alpha[S]);
			seen[alpha[S] - 'a']++;
		}
		res = go(npre, N, S - 1) + res;
	}

	return res;
}

string guess(int N, int S) {
	rep(i,0,S) alpha.push_back('a' + i);
	return go("", N, S - 1);
}

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