Submission #949025

#	Time	Username	Problem	Language	Result	Execution time	Memory
949025		NK_	Password (RMI18_password)	C++17	100 / 100	154 ms	2120 KiB

password

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define sz(x) int(x.size())

using T = pair<int, string>;
#define f first
#define s second
#define mp make_pair

int query(string str);

string guess(int N, int S) {

	priority_queue<T, vector<T>, greater<T>> q;

	for(char c = 'a'; c < 'a' + S; c++) {
		int amt = query(string(N, c));
		q.push(mp(amt, string(amt, c)));
	}

	auto merge = [&](string a, string b) {
		string c = "";
		int j = 0; for(int i = 0; i < sz(a); i++) {	
			while(j < sz(b)) {
				string d = c + b[j] + a.substr(i);
				int left = N - sz(d); d += string(left, a.back());

				int len = query(d);
				if (len != N - left) break;
				c += b[j++];
			}

			c += a[i];
		}

		c += b.substr(j);

		// cout << a << " + " << b << " == " << c << endl;
		return c;
	};

	while(sz(q) > 1) { 
		T a = q.top(); q.pop();
		T b = q.top(); q.pop();

		T c = mp(a.f + b.f, merge(a.s, b.s));
		q.push(c);
	}

	return q.top().s;
}

// g++-13 -std=c++17 -O2 grader.cpp A.cpp -o A

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