Submission #251364

#	Time	Username	Problem	Language	Result	Execution time	Memory
251364		oolimry	Password (RMI18_password)	C++14	100 / 100	624 ms	812 KiB

password

#include <bits/stdc++.h>
using namespace std;
int query(string q);
int cur;
string guess(int n, int s){
	
	vector<char> chars;
	for(int i = 0;i < s;i++) chars.push_back('a' + i);
	
	string tree[2*s];
	
	for(int i = 0;i < s;i++){
		string S = "";
		int pre = 0;
		while(true){
			S += chars[i];
			cur = query(S);
			if(pre == cur) break;
			pre = cur;
		}
		S.pop_back();
		tree[s+i] = S;
	}
	
	
	for(int i = s-1;i >= 1;i--){
		string L = tree[i<<1]; string R = tree[i<<1|1];
		
		int cnt = R.size();
		vector<int> pos[R.size()+1];
		
		int p = 0;		
		for(int l = 0;l < (int) L.size();){
			string S;
			if(p == (int) R.size()){
				for(int j = l;j < (int) L.size();j++) pos[p].push_back(j);
				break;
			}
			cnt++;
			
			pos[p].push_back(l);
			
			for(int j = 0;j < (int) R.size();j++){
				for(int c : pos[j]){
					S += L[c];
				}
				S += R[j];
			}
			
			cur = query(S);
			//cout << cnt << "\n";
			if(cur != cnt){
				pos[p].pop_back();
				p++;
				cnt--;
			}
			else{
				l++;
			}			
		}
		
		string S;
					
		for(int j = 0;j <= (int) R.size();j++){
			for(int c : pos[j]){
				S += L[c];
			}
			if(j != (int) R.size()) S += R[j];
		}
		
		//cout << i << " " << S << "\n";
		tree[i] = S;
	}
	
	
	
	return tree[1];
}

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