oj.uz

Submission #242555

# Submission time Handle Problem Language Result Execution time Memory
242555 2020-06-28T07:56:23 Z tjd229 Password (RMI18_password) C++14
100 / 100
 285 ms 800 KB 
#include <string>
using namespace std;

extern int query(string str);
int cnt[26];

string dc(int s,int e) {
	if (s == e) {
		string res(cnt[s], 'a' + s);
		return res;
	}
	int m = (s + e) >> 1;
	string left = dc(s, m);
	string right = dc(m + 1, e);
	if (left.size() == 0) return right;
	if (right.size() == 0) return left;
	string res = "";
	int l = 0, r = 0;
	while (l < left.size() && r < right.size()) {
		int len = query(res + left[l] + right.substr(r));
		int base = res.size() + right.size() - r;
		if (len > base) res += left[l++];
		else res += right[r++];
	}
	if (l < left.size()) res += left.substr(l);
	else res += right.substr(r);
	
	return res;
}
string guess(int n, int s) {
	for (int i = 0; i < s; ++i) {
		string str(n, 'a' + i);
		cnt[i] = query(str);
	}

	return dc(0,s-1);
}

Compilation message

password.cpp: In function 'std::__cxx11::string dc(int, int)':
password.cpp:20:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (l < left.size() && r < right.size()) {
         ~~^~~~~~~~~~~~~
password.cpp:20:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (l < left.size() && r < right.size()) {
                            ~~^~~~~~~~~~~~~~
password.cpp:26:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (l < left.size()) res += left.substr(l);
      ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 504 KB Guessed the password with 3456 queries.
2 Correct 48 ms 256 KB Guessed the password with 5025 queries.
3 Correct 68 ms 256 KB Guessed the password with 6352 queries.
4 Correct 86 ms 500 KB Guessed the password with 8693 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Guessed the password with 61 queries.
2 Correct 5 ms 384 KB Guessed the password with 101 queries.
3 Correct 4 ms 256 KB Guessed the password with 49 queries.
4 Correct 6 ms 256 KB Guessed the password with 117 queries.
5 Correct 6 ms 256 KB Guessed the password with 92 queries.
6 Correct 6 ms 384 KB Guessed the password with 197 queries.
7 Correct 37 ms 504 KB Guessed the password with 3456 queries.
8 Correct 48 ms 256 KB Guessed the password with 5025 queries.
9 Correct 68 ms 256 KB Guessed the password with 6352 queries.
10 Correct 86 ms 500 KB Guessed the password with 8693 queries.
11 Correct 157 ms 504 KB Guessed the password with 13638 queries.
12 Correct 144 ms 504 KB Guessed the password with 12459 queries.
13 Correct 152 ms 504 KB Guessed the password with 14392 queries.
14 Correct 146 ms 384 KB Guessed the password with 13937 queries.
15 Correct 170 ms 504 KB Guessed the password with 15073 queries.
16 Correct 141 ms 504 KB Guessed the password with 14154 queries.
17 Correct 159 ms 376 KB Guessed the password with 16054 queries.
18 Correct 178 ms 504 KB Guessed the password with 15189 queries.
19 Correct 193 ms 632 KB Guessed the password with 16410 queries.
20 Correct 126 ms 384 KB Guessed the password with 14247 queries.
21 Correct 156 ms 504 KB Guessed the password with 16849 queries.
22 Correct 219 ms 504 KB Guessed the password with 15315 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Guessed the password with 61 queries.
2 Correct 5 ms 384 KB Guessed the password with 101 queries.
3 Correct 4 ms 256 KB Guessed the password with 49 queries.
4 Correct 6 ms 256 KB Guessed the password with 117 queries.
5 Correct 6 ms 256 KB Guessed the password with 92 queries.
6 Correct 6 ms 384 KB Guessed the password with 197 queries.
7 Correct 37 ms 504 KB Guessed the password with 3456 queries.
8 Correct 48 ms 256 KB Guessed the password with 5025 queries.
9 Correct 68 ms 256 KB Guessed the password with 6352 queries.
10 Correct 86 ms 500 KB Guessed the password with 8693 queries.
11 Correct 157 ms 504 KB Guessed the password with 13638 queries.
12 Correct 144 ms 504 KB Guessed the password with 12459 queries.
13 Correct 152 ms 504 KB Guessed the password with 14392 queries.
14 Correct 146 ms 384 KB Guessed the password with 13937 queries.
15 Correct 170 ms 504 KB Guessed the password with 15073 queries.
16 Correct 141 ms 504 KB Guessed the password with 14154 queries.
17 Correct 159 ms 376 KB Guessed the password with 16054 queries.
18 Correct 178 ms 504 KB Guessed the password with 15189 queries.
19 Correct 193 ms 632 KB Guessed the password with 16410 queries.
20 Correct 126 ms 384 KB Guessed the password with 14247 queries.
21 Correct 156 ms 504 KB Guessed the password with 16849 queries.
22 Correct 219 ms 504 KB Guessed the password with 15315 queries.
23 Correct 280 ms 544 KB Guessed the password with 23612 queries.
24 Correct 231 ms 544 KB Guessed the password with 22226 queries.
25 Correct 285 ms 800 KB Guessed the password with 23794 queries.
26 Correct 250 ms 664 KB Guessed the password with 23332 queries.
27 Correct 261 ms 648 KB Guessed the password with 23763 queries.
28 Correct 250 ms 648 KB Guessed the password with 23045 queries.
29 Correct 283 ms 528 KB Guessed the password with 23847 queries.
30 Correct 209 ms 452 KB Guessed the password with 22506 queries.