Submission #733461

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
733461	2023-04-30T19:38:49 Z	rainboy	Password (RMI18_password)	C	100 / 100	215 ms	404 KB

password

#include <string.h>

#define N	5000
#define A	26

int query(char *s);

static int ii[A + 1], n, nl, nr, a_; static char cc[N + 1], cc_[N + 1];

void solve(int l, int r) {
	int m, h, i, j;

	if (r - l == 1) {
		memset(cc + ii[l], l + 'a', (ii[r] - ii[l]) * sizeof *cc);
		return;
	}
	m = (l + r) / 2;
	solve(l, m), solve(m, r);
	nl = ii[m] - ii[l], nr = ii[r] - ii[m];
	memcpy(cc_, cc + ii[l], nl * sizeof *cc_);
	for (i = 0, j = 0; i < nl; i++)
		while (j < nr) {
			for (h = nl + j; h > i + j; h--)
				cc_[h] = cc_[h - 1];
			cc_[i + j] = cc[ii[m] + j];
			cc_[nl + j + 1] = 0;
			if (query(cc_) != nl + j + 1) {
				for (h = i + j; h < nl + j; h++)
					cc_[h] = cc_[h + 1];
				break;
			}
			j++;
		}
	while (j < nr)
		cc_[nl + j] = cc[ii[m] + j], j++;
	memcpy(cc + ii[l], cc_, (nl + nr) * sizeof *cc_);
}

char *guess(int n_, int a__) {
	int a;

	n = n_, a_ = a__;
	ii[0] = 0;
	for (a = 0; a < a_; a++) {
		memset(cc, a + 'a', n * sizeof *cc), cc[n] = 0;
		ii[a + 1] = ii[a] + query(cc);
	}
	solve(0, a_);
	cc[n] = 0;
	return cc;
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Guessed the password with 58 queries.
2	Correct	2 ms	208 KB	Guessed the password with 97 queries.

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Guessed the password with 48 queries.
2	Correct	1 ms	208 KB	Guessed the password with 90 queries.
3	Correct	2 ms	208 KB	Guessed the password with 170 queries.
4	Correct	3 ms	208 KB	Guessed the password with 198 queries.

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	208 KB	Guessed the password with 3514 queries.
2	Correct	42 ms	208 KB	Guessed the password with 4971 queries.
3	Correct	40 ms	208 KB	Guessed the password with 6481 queries.
4	Correct	47 ms	208 KB	Guessed the password with 8887 queries.

Subtask #4

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Guessed the password with 58 queries.
2	Correct	2 ms	208 KB	Guessed the password with 97 queries.
3	Correct	1 ms	208 KB	Guessed the password with 48 queries.
4	Correct	1 ms	208 KB	Guessed the password with 90 queries.
5	Correct	2 ms	208 KB	Guessed the password with 170 queries.
6	Correct	3 ms	208 KB	Guessed the password with 198 queries.
7	Correct	37 ms	208 KB	Guessed the password with 3514 queries.
8	Correct	42 ms	208 KB	Guessed the password with 4971 queries.
9	Correct	40 ms	208 KB	Guessed the password with 6481 queries.
10	Correct	47 ms	208 KB	Guessed the password with 8887 queries.
11	Correct	129 ms	208 KB	Guessed the password with 12697 queries.
12	Correct	84 ms	208 KB	Guessed the password with 13443 queries.
13	Correct	88 ms	208 KB	Guessed the password with 13923 queries.
14	Correct	114 ms	208 KB	Guessed the password with 14382 queries.
15	Correct	88 ms	208 KB	Guessed the password with 14441 queries.
16	Correct	111 ms	208 KB	Guessed the password with 14910 queries.
17	Correct	90 ms	256 KB	Guessed the password with 14953 queries.
18	Correct	123 ms	208 KB	Guessed the password with 16131 queries.
19	Correct	128 ms	208 KB	Guessed the password with 15123 queries.
20	Correct	87 ms	208 KB	Guessed the password with 15400 queries.
21	Correct	141 ms	208 KB	Guessed the password with 15961 queries.
22	Correct	154 ms	208 KB	Guessed the password with 16275 queries.

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Guessed the password with 58 queries.
2	Correct	2 ms	208 KB	Guessed the password with 97 queries.
3	Correct	1 ms	208 KB	Guessed the password with 48 queries.
4	Correct	1 ms	208 KB	Guessed the password with 90 queries.
5	Correct	2 ms	208 KB	Guessed the password with 170 queries.
6	Correct	3 ms	208 KB	Guessed the password with 198 queries.
7	Correct	37 ms	208 KB	Guessed the password with 3514 queries.
8	Correct	42 ms	208 KB	Guessed the password with 4971 queries.
9	Correct	40 ms	208 KB	Guessed the password with 6481 queries.
10	Correct	47 ms	208 KB	Guessed the password with 8887 queries.
11	Correct	129 ms	208 KB	Guessed the password with 12697 queries.
12	Correct	84 ms	208 KB	Guessed the password with 13443 queries.
13	Correct	88 ms	208 KB	Guessed the password with 13923 queries.
14	Correct	114 ms	208 KB	Guessed the password with 14382 queries.
15	Correct	88 ms	208 KB	Guessed the password with 14441 queries.
16	Correct	111 ms	208 KB	Guessed the password with 14910 queries.
17	Correct	90 ms	256 KB	Guessed the password with 14953 queries.
18	Correct	123 ms	208 KB	Guessed the password with 16131 queries.
19	Correct	128 ms	208 KB	Guessed the password with 15123 queries.
20	Correct	87 ms	208 KB	Guessed the password with 15400 queries.
21	Correct	141 ms	208 KB	Guessed the password with 15961 queries.
22	Correct	154 ms	208 KB	Guessed the password with 16275 queries.
23	Correct	207 ms	404 KB	Guessed the password with 23566 queries.
24	Correct	160 ms	392 KB	Guessed the password with 22883 queries.
25	Correct	193 ms	344 KB	Guessed the password with 23760 queries.
26	Correct	158 ms	388 KB	Guessed the password with 23461 queries.
27	Correct	176 ms	296 KB	Guessed the password with 23801 queries.
28	Correct	215 ms	300 KB	Guessed the password with 22181 queries.
29	Correct	116 ms	296 KB	Guessed the password with 23809 queries.
30	Correct	195 ms	352 KB	Guessed the password with 21106 queries.