oj.uz

Submission #331746

# Submission time Handle Problem Language Result Execution time Memory
331746 2020-11-29T21:29:23 Z dolphingarlic Password (RMI18_password) C++14
100 / 100
 290 ms 808 KB 
#include <string>
using namespace std;

int query(string str);

string solve(int l, int r, int n) {
	if (l == r) {
		string to_guess = "";
		for (int i = 0; i < n; i++) to_guess += 'a' + l;
		int len = query(to_guess);
		return string(len, 'a' + l);
	} else {
		int mid = (l + r) / 2;
		string a = solve(l, mid, n), b = solve(mid + 1, r, n);
		int a_ptr = 0, b_ptr = 0;
		string known = "";
		while (a_ptr < a.size() && b_ptr < b.size()) {
			string to_guess = known + a[a_ptr] + b.substr(b_ptr);
			int prev_len = known.size() + b.size() - b_ptr;
			if (query(to_guess) > prev_len) known += a[a_ptr++];
			else known += b[b_ptr++];
		}
		if (a_ptr < a.size()) known += a.substr(a_ptr);
		else known += b.substr(b_ptr);
		return known;
	}
}

string guess(int n, int s) { return solve(0, s - 1, n); }

Compilation message

password.cpp: In function 'std::string solve(int, int, int)':
password.cpp:17:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   while (a_ptr < a.size() && b_ptr < b.size()) {
      |          ~~~~~~^~~~~~~~~~
password.cpp:17:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   while (a_ptr < a.size() && b_ptr < b.size()) {
      |                              ~~~~~~^~~~~~~~~~
password.cpp:23:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   if (a_ptr < a.size()) known += a.substr(a_ptr);
      |       ~~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 61 queries.
2 Correct 2 ms 364 KB Guessed the password with 101 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 49 queries.
2 Correct 2 ms 364 KB Guessed the password with 117 queries.
3 Correct 2 ms 364 KB Guessed the password with 92 queries.
4 Correct 3 ms 364 KB Guessed the password with 197 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 496 KB Guessed the password with 3456 queries.
2 Correct 47 ms 428 KB Guessed the password with 5025 queries.
3 Correct 62 ms 364 KB Guessed the password with 6352 queries.
4 Correct 98 ms 492 KB Guessed the password with 8693 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 61 queries.
2 Correct 2 ms 364 KB Guessed the password with 101 queries.
3 Correct 1 ms 364 KB Guessed the password with 49 queries.
4 Correct 2 ms 364 KB Guessed the password with 117 queries.
5 Correct 2 ms 364 KB Guessed the password with 92 queries.
6 Correct 3 ms 364 KB Guessed the password with 197 queries.
7 Correct 48 ms 496 KB Guessed the password with 3456 queries.
8 Correct 47 ms 428 KB Guessed the password with 5025 queries.
9 Correct 62 ms 364 KB Guessed the password with 6352 queries.
10 Correct 98 ms 492 KB Guessed the password with 8693 queries.
11 Correct 161 ms 500 KB Guessed the password with 13638 queries.
12 Correct 167 ms 492 KB Guessed the password with 12459 queries.
13 Correct 143 ms 628 KB Guessed the password with 14392 queries.
14 Correct 147 ms 572 KB Guessed the password with 13937 queries.
15 Correct 190 ms 632 KB Guessed the password with 15073 queries.
16 Correct 173 ms 572 KB Guessed the password with 14154 queries.
17 Correct 169 ms 628 KB Guessed the password with 16054 queries.
18 Correct 148 ms 492 KB Guessed the password with 15189 queries.
19 Correct 195 ms 584 KB Guessed the password with 16410 queries.
20 Correct 155 ms 796 KB Guessed the password with 14247 queries.
21 Correct 125 ms 364 KB Guessed the password with 16849 queries.
22 Correct 152 ms 568 KB Guessed the password with 15315 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 61 queries.
2 Correct 2 ms 364 KB Guessed the password with 101 queries.
3 Correct 1 ms 364 KB Guessed the password with 49 queries.
4 Correct 2 ms 364 KB Guessed the password with 117 queries.
5 Correct 2 ms 364 KB Guessed the password with 92 queries.
6 Correct 3 ms 364 KB Guessed the password with 197 queries.
7 Correct 48 ms 496 KB Guessed the password with 3456 queries.
8 Correct 47 ms 428 KB Guessed the password with 5025 queries.
9 Correct 62 ms 364 KB Guessed the password with 6352 queries.
10 Correct 98 ms 492 KB Guessed the password with 8693 queries.
11 Correct 161 ms 500 KB Guessed the password with 13638 queries.
12 Correct 167 ms 492 KB Guessed the password with 12459 queries.
13 Correct 143 ms 628 KB Guessed the password with 14392 queries.
14 Correct 147 ms 572 KB Guessed the password with 13937 queries.
15 Correct 190 ms 632 KB Guessed the password with 15073 queries.
16 Correct 173 ms 572 KB Guessed the password with 14154 queries.
17 Correct 169 ms 628 KB Guessed the password with 16054 queries.
18 Correct 148 ms 492 KB Guessed the password with 15189 queries.
19 Correct 195 ms 584 KB Guessed the password with 16410 queries.
20 Correct 155 ms 796 KB Guessed the password with 14247 queries.
21 Correct 125 ms 364 KB Guessed the password with 16849 queries.
22 Correct 152 ms 568 KB Guessed the password with 15315 queries.
23 Correct 287 ms 660 KB Guessed the password with 23612 queries.
24 Correct 264 ms 644 KB Guessed the password with 22226 queries.
25 Correct 261 ms 664 KB Guessed the password with 23794 queries.
26 Correct 290 ms 808 KB Guessed the password with 23332 queries.
27 Correct 232 ms 700 KB Guessed the password with 23763 queries.
28 Correct 237 ms 612 KB Guessed the password with 23045 queries.
29 Correct 229 ms 748 KB Guessed the password with 23847 queries.
30 Correct 214 ms 784 KB Guessed the password with 22506 queries.