Submission #661030

#	Time	Username	Problem	Language	Result	Execution time	Memory
661030		angelo_torres	Password (RMI18_password)	C++17	100 / 100	700 ms	820 KiB

password

#include <bits/stdc++.h>
#define sz(v) (int) v.size()
#define ff first
#define ss second
 
using namespace std;
typedef pair<int,int> ii;
 
int cn[26];
vector<int> a[26];
// 6 6 7 7
vector<vector<int>> rn(4);
deque<pair<int,char>> gr[4];
char ans[5005];
 
int query(string q);
// int query(string s){
// 	cout << s << endl;
// 	int tr; cin >> tr;
// 	return tr;
// }
vector<int> po;

int com(int i1,int i2,int id,int nn){
	if(i1 == -1) return i2;
	if(i2 == -1) return i1;
	string tr = "";
	for(auto it : gr[i1]) tr.push_back(it.ss);
	tr.push_back(gr[i2].back().ss);
	for(int i = id+1; i <= nn; ++i) tr.push_back(ans[i]);
	if(query(tr) == sz(tr)) return i2;
	return i1;
}

string guess(int n,int s){
	// [0,7] 
	// [8,16]
	// [17,25]
	rn[0] = {0,1,2,3,4,5,25};
	rn[1] = {6,7,8,9,10,11};
	rn[2] = {12,13,14,15,16,17};
	rn[3] = {18,19,20,21,22,23,24};
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	for(int i = 0; i < s; ++i) cn[i] = n;
	for(int id = 0; id < 4; ++id){
		vector<int> it = rn[id];
		for(int i : it){
			for(int j : it){
				if(i == j or i >= s or j >= s) continue;
				char x = (char) ('a'+i), y = (char) ('a'+j);
				string tr = "";
				for(int k = 1; k <= n; ++k) tr.push_back(y);
				for(int k = 1; k <= cn[i]; ++k){
					tr[k-1] = x;
					int vl = query(tr);
					if(vl < k) break;
					if(sz(a[i]) < k) a[i].push_back(vl-k);
					else a[i][k-1] += (vl-k);
				}
				cn[i] = sz(a[i]);
			}
		}
		// cout << endl;
	}
	for(int i = 0; i < 26; ++i) cn[i] = sz(a[i]);
	for(int i = 0; i < 26; ++i){
		for(int j = 0; j < sz(a[i]); ++j) a[i][j] += (sz(a[i])-j-1);
	}
	for(int id = 0; id < 4; ++id){
		vector<int> vi = rn[id];
		for(int j : vi){
			for(auto it : a[j]) gr[id].push_back({it,((char) ('a'+j))});
		}
		sort(gr[id].begin(), gr[id].end(), greater<pair<int,char>>());
		// for(auto it : gr[id]) cout << it.ff << " " << it.ss << " ";
		// cout << endl;
	} 
	for(int i = n; i >= 1; --i){
		for(int j = 0; j < 4; ++j){
			if(sz(gr[j]) > 0 && gr[j].back().ff == n-i) po.push_back(j);
		}
		int rp = -1;
		for(int j = 0; j < sz(po); ++j) rp = com(rp,po[j],i,n);
		ans[i] = gr[rp].back().ss;
		gr[rp].pop_back();
		for(int j = 0; j < 4; ++j){
			if(j == rp) continue;
			for(auto &it : gr[j]) it.ff++;
		} 
		po.clear();
	}
	string tt = "";
	for(int i = 1; i <= n; ++i) tt.push_back(ans[i]);
	return tt;
}
 
// int main(){
// 	int n,s; cin >> n >> s;
// 	cout << guess(n,s) << endl;
// 	return 0;
// }

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