Submission #342342

#	Time	Username	Problem	Language	Result	Execution time	Memory
342342		Gajowy	Password (RMI18_password)	C++14	80 / 100	967 ms	772 KiB

password

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

int query(string str);

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;
			for(int l=1;l<=qres;l++){
				int lo=0,hi=res.size();
				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<l;i++)
						qs.push_back(c);
					int smqres=query(qs);
					if(smqres==(int)qs.size())
						lo=mid;
					else
						hi=mid-1;
				}
				pos.push_back(lo);
			}
			reverse(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: 0 / 20