Submission #733460

#	Time	Username	Problem	Language	Result	Execution time	Memory
733460		rainboy	Password (RMI18_password)	C11	0 / 100	9 ms	208 KiB

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_) != i + j) {
				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++;
}

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: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20