Submission #394150

#	Time	Username	Problem	Language	Result	Execution time	Memory
394150		jsannemo	Password (RMI18_password)	C++14	50 / 100	1682 ms	41504 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> rem(26);

string go(const string& pre, const string& post, int N, int S) {
	if (S < 0) return "";

	int cnt = 0;
	string mid(1, 'a' + S);
	if (rem[S] && query(pre + mid + post) == sz(pre) + 1 + sz(post)) {
		int hi = sz(pre) + sz(post) + rem[S] + 1;
		int lo = sz(pre) + sz(post) + 1;
		while (hi - lo > 1) {
			int mid = (lo + hi) / 2;
			cerr << "test tot length " << mid << " of char" << endl;

			string ask = pre;
			rep(i,0,mid - sz(pre) - sz(post)) ask.push_back('a' + S);
			ask.insert(ask.end(), post.begin(), post.end());
			int cnt = query(ask);
			if (cnt >= mid) lo = mid;
			else hi = mid;
		}
		cnt = lo - sz(pre) - sz(post);
	}

	cerr << "with pre " << pre << " and post " << post << " at " << (char)(S+'a') << " we found " << cnt << endl;

	string res;
	rep(i,0,cnt + 1) {
		string npre = pre;
		rep(j,0,i) npre.push_back('a' + S);

		string npost;
		rep(j,0,cnt-i) npost.push_back('a' + S);
		npost += post;

		res += go(npre, npost, N - sz(res) + i, S - 1);
		if (i != cnt) {
			res.push_back('a' + S);
			rem[S]--;
		}
	}

	return res;
}

string guess(int N, int S) {
	rep(i,0,S) {
		string s(N, 'a' + i);
		rem[i] = query(s);
	}
	return go("", "", N, S - 1);
}

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