Submission #709137

#	Time	Username	Problem	Language	Result	Execution time	Memory
709137		jamezzz	Password (RMI18_password)	C++17	100 / 100	153 ms	600 KiB

password

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

int query(string str);

string ans="";
vector<pair<int,int>> res;

void dnc(int l,int r,int num,char c,int n,int rside){
	//printf("dnc %d %d %d %c %d:\n",l,r,num,c,n);
	if(num==0)return;
	if(l==r){
		res.push_back({l,num});
		return;
	}
	int m=((l+r)>>1)+1;
	string tmp=ans;
	tmp.resize(m);
	tmp+=string(min(num,n-rside-m)+rside,c);
	int qres=query(tmp)-m-rside;
	//cout<<tmp<<' '<<qres<<endl;
	int lnum=num-qres;
	int rnum=qres;
	tmp.clear();
	dnc(l,m-1,lnum,c,n,rnum+rside);
	dnc(m,r,rnum,c,n,rside);
}

string guess(int n,int s){
	for(int i=0;i<s;++i){
		char c='a'+i;
		//printf("%c\n",c);
		int num=query(string(n,c));
		dnc(0,ans.length(),num,c,n,0);
		int off=0;
		for(auto[pos,num]:res){
			ans.insert(pos+off,num,c);
			off+=num;
		}
		res.clear();
		//cout<<ans<<endl;
	}
	return ans;
}

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