oj.uz

답안 #251362

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
251362 2020-07-21T02:40:57 Z shenxy Password (RMI18_password) C++14
100 / 100
 255 ms 744 KB 
#include <algorithm>
#include <string>
using namespace std;
int cnt[26];
int query(string str);
string dnc(int s, int e) {
	if (s == e) {
		string ans = "";
		for (int i = 0; i < cnt[s]; ++i) ans.push_back('a' + s);
		return ans;
	}
	string l = dnc(s, (s + e) / 2), r = dnc((s + e) / 2 + 1, e);
	int ptr = 0;
	for (char c: r) {
		string x = l;
		x.insert(ptr, 1, c);
		while (query(x) != x.length()) x = l, x.insert(++ptr, 1, c);
		l = x;
		++ptr;
	}
	return l;
}
string guess(int N, int S) {
	for (int i = 0; i < S; ++i) {
		string Q = "";
		for (int j = 0; j < N; ++j) Q.push_back('a' + i);
		cnt[i] = query(Q);
	}
	return dnc(0, S - 1);
}

Compilation message

password.cpp: In function 'std::__cxx11::string dnc(int, int)':
password.cpp:17:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (query(x) != x.length()) x = l, x.insert(++ptr, 1, c);
          ~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Guessed the password with 68 queries.
2 Correct 2 ms 256 KB Guessed the password with 111 queries.

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Guessed the password with 48 queries.
2 Correct 2 ms 256 KB Guessed the password with 116 queries.
3 Correct 1 ms 256 KB Guessed the password with 93 queries.
4 Correct 2 ms 256 KB Guessed the password with 203 queries.

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 256 KB Guessed the password with 3704 queries.
2 Correct 39 ms 376 KB Guessed the password with 5053 queries.
3 Correct 68 ms 376 KB Guessed the password with 6584 queries.
4 Correct 86 ms 376 KB Guessed the password with 8721 queries.

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Guessed the password with 68 queries.
2 Correct 2 ms 256 KB Guessed the password with 111 queries.
3 Correct 1 ms 256 KB Guessed the password with 48 queries.
4 Correct 2 ms 256 KB Guessed the password with 116 queries.
5 Correct 1 ms 256 KB Guessed the password with 93 queries.
6 Correct 2 ms 256 KB Guessed the password with 203 queries.
7 Correct 36 ms 256 KB Guessed the password with 3704 queries.
8 Correct 39 ms 376 KB Guessed the password with 5053 queries.
9 Correct 68 ms 376 KB Guessed the password with 6584 queries.
10 Correct 86 ms 376 KB Guessed the password with 8721 queries.
11 Correct 107 ms 504 KB Guessed the password with 13682 queries.
12 Correct 136 ms 504 KB Guessed the password with 12654 queries.
13 Correct 148 ms 376 KB Guessed the password with 14410 queries.
14 Correct 113 ms 500 KB Guessed the password with 13979 queries.
15 Correct 109 ms 376 KB Guessed the password with 15314 queries.
16 Correct 127 ms 504 KB Guessed the password with 14485 queries.
17 Correct 140 ms 376 KB Guessed the password with 16114 queries.
18 Correct 156 ms 376 KB Guessed the password with 15294 queries.
19 Correct 169 ms 376 KB Guessed the password with 16485 queries.
20 Correct 140 ms 504 KB Guessed the password with 15088 queries.
21 Correct 165 ms 504 KB Guessed the password with 16990 queries.
22 Correct 158 ms 384 KB Guessed the password with 15908 queries.

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Guessed the password with 68 queries.
2 Correct 2 ms 256 KB Guessed the password with 111 queries.
3 Correct 1 ms 256 KB Guessed the password with 48 queries.
4 Correct 2 ms 256 KB Guessed the password with 116 queries.
5 Correct 1 ms 256 KB Guessed the password with 93 queries.
6 Correct 2 ms 256 KB Guessed the password with 203 queries.
7 Correct 36 ms 256 KB Guessed the password with 3704 queries.
8 Correct 39 ms 376 KB Guessed the password with 5053 queries.
9 Correct 68 ms 376 KB Guessed the password with 6584 queries.
10 Correct 86 ms 376 KB Guessed the password with 8721 queries.
11 Correct 107 ms 504 KB Guessed the password with 13682 queries.
12 Correct 136 ms 504 KB Guessed the password with 12654 queries.
13 Correct 148 ms 376 KB Guessed the password with 14410 queries.
14 Correct 113 ms 500 KB Guessed the password with 13979 queries.
15 Correct 109 ms 376 KB Guessed the password with 15314 queries.
16 Correct 127 ms 504 KB Guessed the password with 14485 queries.
17 Correct 140 ms 376 KB Guessed the password with 16114 queries.
18 Correct 156 ms 376 KB Guessed the password with 15294 queries.
19 Correct 169 ms 376 KB Guessed the password with 16485 queries.
20 Correct 140 ms 504 KB Guessed the password with 15088 queries.
21 Correct 165 ms 504 KB Guessed the password with 16990 queries.
22 Correct 158 ms 384 KB Guessed the password with 15908 queries.
23 Correct 251 ms 476 KB Guessed the password with 23708 queries.
24 Correct 214 ms 460 KB Guessed the password with 22770 queries.
25 Correct 217 ms 488 KB Guessed the password with 23853 queries.
26 Correct 227 ms 688 KB Guessed the password with 23374 queries.
27 Correct 255 ms 488 KB Guessed the password with 23807 queries.
28 Correct 229 ms 744 KB Guessed the password with 23436 queries.
29 Correct 208 ms 416 KB Guessed the password with 23873 queries.
30 Correct 220 ms 532 KB Guessed the password with 23818 queries.