Submission #251436

#	Time	Username	Problem	Language	Result	Execution time	Memory
251436		lyc	Password (RMI18_password)	C++14	100 / 100	317 ms	688 KiB

password

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

#define TRACE(x) cerr << #x << " :: ";
#define _ << " " <<
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())

int query(string Q);

string solve(vector<string>& vec, int l, int r) {
	if (l == r) return vec[l];
	
	int m = (l+r)>>1;
	string x = solve(vec,l,m), y = solve(vec,m+1,r);
	
	string S = "";
	int i, j;
	for (i = 0, j = 0; i < SZ(x) && j < SZ(y);) {
		string T = S + y[j] + x.substr(i);
		int q = query(T);
		if (q == SZ(T)) S += y[j++];
		else S += x[i++];
	}
	if (i < SZ(x)) S += x.substr(i);
	if (j < SZ(y)) S += y.substr(j);
	return S;
}

string guess(int N, int S) {
	vector<string> vec;
	FOR(i,0,S-1){
		string s(N,'a'+i);
		int freq = query(s);
		vec.push_back(string(freq,'a'+i));
	}
	
	return solve(vec,0,SZ(vec)-1);
}

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