Submission #342346

#	Time	Username	Problem	Language	Result	Execution time	Memory
342346		Gajowy	Password (RMI18_password)	C++14	100 / 100	473 ms	872 KiB

password

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

int query(string str);

void solve_positions(char c,string &res,int l,int r,int pl,int pr,vector<int> &resvec){
	int len=(l+r)/2;
	int lo=pl,hi=pr;
	string qs;
	while(lo<hi){
		qs.clear();
		int mid=(lo+hi)/2+1;
		for(int i=0;i<mid;i++)
			qs.push_back(res[i]);
		for(int i=0;i<len;i++)
			qs.push_back(c);
		int smqres=query(qs);
		if(smqres==(int)qs.size())
			lo=mid;
		else
			hi=mid-1;
	}
	resvec.push_back(lo);
	if(len-1>=l)
		solve_positions(c,res,l,len-1,lo,pr,resvec);
	if(len+1<=r)
		solve_positions(c,res,len+1,r,pl,lo,resvec);
}

string guess(int n,int s){
	string res;
	string qs;
	vector<int> cnts(s);
	for(int cc=0;cc<s;cc++){
		char c=(char)('a'+cc);
		qs.clear();
		for(int i=0;i<n;i++)
			qs.push_back(c);
		int qres=query(qs);
		cnts[cc]=qres;
	}
	vector<pair<int,int>> srt;
	for(int i=0;i<s;i++)
		srt.push_back(make_pair(cnts[i],i));
	sort(begin(srt),end(srt),greater<pair<int,int>>());
	for(int cc=0;cc<s;cc++){
		char c=(char)('a'+srt[cc].second);
		int maxcount=srt[cc].first;
		qs.clear();
		if(res.size()==0){
			int qres=maxcount;
			for(int i=0;i<qres;i++)
				res.push_back(c);
		}
		else
		if((int)res.size()<n){
			int qres=maxcount;
			if(qres==0)
				continue;
			vector<int> pos;
			solve_positions(c,res,1,qres,0,res.size(),pos);
			sort(begin(pos),end(pos));
			string new_res;
			for(int i=res.size();i>=0;i--){
				while(pos.size()>0&&pos.back()>=i)
					new_res.push_back(c),pos.pop_back();
				if(i!=0)
					new_res.push_back(res[i-1]);
			}
			reverse(begin(new_res),end(new_res));
			res=new_res;
		}
	}
	return res;
}

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