제출 #394148

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
394148		jsannemo	Password (RMI18_password)	C++14	30 / 100	412 ms	2368 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 hi = sz(pre) + sz(post) + rem[S] + 1;
	int lo = sz(pre) + sz(post);
	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;
	}

	int 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: 0 / 20
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20