Submission #949025

# Submission time Handle Problem Language Result Execution time Memory
949025 2024-03-18T19:54:29 Z NK_ Password (RMI18_password) C++17
100 / 100
154 ms 2120 KB
// 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
# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 57 queries.
2 Correct 1 ms 592 KB Guessed the password with 104 queries.
# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Guessed the password with 48 queries.
2 Correct 1 ms 344 KB Guessed the password with 91 queries.
3 Correct 1 ms 344 KB Guessed the password with 91 queries.
4 Correct 1 ms 436 KB Guessed the password with 179 queries.
# Verdict Execution time Memory Grader output
1 Correct 14 ms 1208 KB Guessed the password with 2751 queries.
2 Correct 27 ms 468 KB Guessed the password with 5071 queries.
3 Correct 19 ms 724 KB Guessed the password with 4587 queries.
4 Correct 41 ms 692 KB Guessed the password with 8085 queries.
# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 57 queries.
2 Correct 1 ms 592 KB Guessed the password with 104 queries.
3 Correct 1 ms 596 KB Guessed the password with 48 queries.
4 Correct 1 ms 344 KB Guessed the password with 91 queries.
5 Correct 1 ms 344 KB Guessed the password with 91 queries.
6 Correct 1 ms 436 KB Guessed the password with 179 queries.
7 Correct 14 ms 1208 KB Guessed the password with 2751 queries.
8 Correct 27 ms 468 KB Guessed the password with 5071 queries.
9 Correct 19 ms 724 KB Guessed the password with 4587 queries.
10 Correct 41 ms 692 KB Guessed the password with 8085 queries.
11 Correct 51 ms 720 KB Guessed the password with 8155 queries.
12 Correct 41 ms 956 KB Guessed the password with 8161 queries.
13 Correct 58 ms 996 KB Guessed the password with 11503 queries.
14 Correct 62 ms 492 KB Guessed the password with 11603 queries.
15 Correct 57 ms 988 KB Guessed the password with 10881 queries.
16 Correct 54 ms 956 KB Guessed the password with 10860 queries.
17 Correct 53 ms 952 KB Guessed the password with 10212 queries.
18 Correct 53 ms 1464 KB Guessed the password with 10246 queries.
19 Correct 47 ms 736 KB Guessed the password with 9687 queries.
20 Correct 52 ms 1232 KB Guessed the password with 9776 queries.
21 Correct 57 ms 736 KB Guessed the password with 11640 queries.
22 Correct 57 ms 1204 KB Guessed the password with 11709 queries.
# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 57 queries.
2 Correct 1 ms 592 KB Guessed the password with 104 queries.
3 Correct 1 ms 596 KB Guessed the password with 48 queries.
4 Correct 1 ms 344 KB Guessed the password with 91 queries.
5 Correct 1 ms 344 KB Guessed the password with 91 queries.
6 Correct 1 ms 436 KB Guessed the password with 179 queries.
7 Correct 14 ms 1208 KB Guessed the password with 2751 queries.
8 Correct 27 ms 468 KB Guessed the password with 5071 queries.
9 Correct 19 ms 724 KB Guessed the password with 4587 queries.
10 Correct 41 ms 692 KB Guessed the password with 8085 queries.
11 Correct 51 ms 720 KB Guessed the password with 8155 queries.
12 Correct 41 ms 956 KB Guessed the password with 8161 queries.
13 Correct 58 ms 996 KB Guessed the password with 11503 queries.
14 Correct 62 ms 492 KB Guessed the password with 11603 queries.
15 Correct 57 ms 988 KB Guessed the password with 10881 queries.
16 Correct 54 ms 956 KB Guessed the password with 10860 queries.
17 Correct 53 ms 952 KB Guessed the password with 10212 queries.
18 Correct 53 ms 1464 KB Guessed the password with 10246 queries.
19 Correct 47 ms 736 KB Guessed the password with 9687 queries.
20 Correct 52 ms 1232 KB Guessed the password with 9776 queries.
21 Correct 57 ms 736 KB Guessed the password with 11640 queries.
22 Correct 57 ms 1204 KB Guessed the password with 11709 queries.
23 Correct 151 ms 2024 KB Guessed the password with 23705 queries.
24 Correct 126 ms 1832 KB Guessed the password with 20966 queries.
25 Correct 142 ms 1996 KB Guessed the password with 23668 queries.
26 Correct 116 ms 1836 KB Guessed the password with 19099 queries.
27 Correct 148 ms 2120 KB Guessed the password with 23702 queries.
28 Correct 113 ms 1840 KB Guessed the password with 16822 queries.
29 Correct 154 ms 1732 KB Guessed the password with 23708 queries.
30 Correct 89 ms 1780 KB Guessed the password with 14392 queries.