oj.uz

Submission #239644

# Submission time Handle Problem Language Result Execution time Memory
239644 2020-06-17T01:37:53 Z luciocf Password (RMI18_password) C++14
100 / 100
 671 ms 684 KB 
#include <bits/stdc++.h>

using namespace std;

int query(string str);

int freq[27];
int nxt[5010];
int mark[5010];

string ans = "";

int qtd(int pos, char c)
{
	if (mark[pos] != -1) return mark[pos];

	string aux = "";

	for (int i = 0; i <= pos; i++)
		aux += ans[i];

	for (int i = 0; i < freq[(int)(c-'a')]; i++)
		aux += c;

	return mark[pos] = (query(aux) - (pos+1));
}

string guess(int n, int s)
{
	freq[s-1] = n;

	for (int i = 0; i < s-1; i++)
	{
		char c = (char)('a'+i);
		string aux = "";

		for (int j = 0; j < n; j++)
			aux += c;

		freq[i] = query(aux);
		freq[s-1] -= freq[i];
	}

	for (int i = 0; i < s; i++)
	{
		if (!freq[i]) continue;

		memset(nxt, 0, sizeof nxt);
		memset(mark, -1, sizeof mark);

		char c = (char)('a'+i);
		int tot = 0;

		if (ans.empty())
		{
			for (int j = 0; j < freq[i]; j++)
				ans += c;
			continue;
		}

		int last = ans.size()-1;

		while (true)
		{
			int ini = 0, fim = last, ind = -1;

			if (tot < freq[i] && qtd(0, c) > tot)
			{
				while (ini <= fim)
				{
					int mid = (ini+fim)>>1;

					if (qtd(mid, c) > tot) ind = mid, ini = mid+1;
					else fim = mid-1;
				}
			}

			if (ind == -1)
			{
				string aux = "";

				for (int j = 0; j < freq[i]-tot; j++)
					aux += c;

				for (int j = 0; j < ans.size(); j++)
				{
					aux += ans[j];

					for (int l = 0; l < nxt[j]; l++)
						aux += c;
				}
				swap(ans, aux);

				break;
			}

			nxt[ind] = qtd(ind, c)-tot;
			tot = qtd(ind, c);
			last = ind-1;
		}
	}

	return ans;
}

Compilation message

password.cpp: In function 'std::__cxx11::string guess(int, int)':
password.cpp:85:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < ans.size(); j++)
                     ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Guessed the password with 20 queries.
2 Correct 6 ms 384 KB Guessed the password with 67 queries.
3 Correct 5 ms 384 KB Guessed the password with 9 queries.
4 Correct 6 ms 384 KB Guessed the password with 112 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 384 KB Guessed the password with 1947 queries.
2 Correct 39 ms 504 KB Guessed the password with 2741 queries.
3 Correct 79 ms 436 KB Guessed the password with 4221 queries.
4 Correct 107 ms 504 KB Guessed the password with 7316 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Guessed the password with 62 queries.
2 Correct 6 ms 384 KB Guessed the password with 109 queries.
3 Correct 5 ms 384 KB Guessed the password with 20 queries.
4 Correct 6 ms 384 KB Guessed the password with 67 queries.
5 Correct 5 ms 384 KB Guessed the password with 9 queries.
6 Correct 6 ms 384 KB Guessed the password with 112 queries.
7 Correct 32 ms 384 KB Guessed the password with 1947 queries.
8 Correct 39 ms 504 KB Guessed the password with 2741 queries.
9 Correct 79 ms 436 KB Guessed the password with 4221 queries.
10 Correct 107 ms 504 KB Guessed the password with 7316 queries.
11 Correct 179 ms 412 KB Guessed the password with 8260 queries.
12 Correct 141 ms 384 KB Guessed the password with 6437 queries.
13 Correct 222 ms 420 KB Guessed the password with 10858 queries.
14 Correct 183 ms 384 KB Guessed the password with 10448 queries.
15 Correct 236 ms 504 KB Guessed the password with 11410 queries.
16 Correct 232 ms 504 KB Guessed the password with 10140 queries.
17 Correct 196 ms 384 KB Guessed the password with 9601 queries.
18 Correct 163 ms 504 KB Guessed the password with 7923 queries.
19 Correct 211 ms 504 KB Guessed the password with 9827 queries.
20 Correct 152 ms 512 KB Guessed the password with 7578 queries.
21 Correct 132 ms 504 KB Guessed the password with 6349 queries.
22 Correct 116 ms 384 KB Guessed the password with 5306 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Guessed the password with 62 queries.
2 Correct 6 ms 384 KB Guessed the password with 109 queries.
3 Correct 5 ms 384 KB Guessed the password with 20 queries.
4 Correct 6 ms 384 KB Guessed the password with 67 queries.
5 Correct 5 ms 384 KB Guessed the password with 9 queries.
6 Correct 6 ms 384 KB Guessed the password with 112 queries.
7 Correct 32 ms 384 KB Guessed the password with 1947 queries.
8 Correct 39 ms 504 KB Guessed the password with 2741 queries.
9 Correct 79 ms 436 KB Guessed the password with 4221 queries.
10 Correct 107 ms 504 KB Guessed the password with 7316 queries.
11 Correct 179 ms 412 KB Guessed the password with 8260 queries.
12 Correct 141 ms 384 KB Guessed the password with 6437 queries.
13 Correct 222 ms 420 KB Guessed the password with 10858 queries.
14 Correct 183 ms 384 KB Guessed the password with 10448 queries.
15 Correct 236 ms 504 KB Guessed the password with 11410 queries.
16 Correct 232 ms 504 KB Guessed the password with 10140 queries.
17 Correct 196 ms 384 KB Guessed the password with 9601 queries.
18 Correct 163 ms 504 KB Guessed the password with 7923 queries.
19 Correct 211 ms 504 KB Guessed the password with 9827 queries.
20 Correct 152 ms 512 KB Guessed the password with 7578 queries.
21 Correct 132 ms 504 KB Guessed the password with 6349 queries.
22 Correct 116 ms 384 KB Guessed the password with 5306 queries.
23 Correct 291 ms 532 KB Guessed the password with 13825 queries.
24 Correct 238 ms 588 KB Guessed the password with 11408 queries.
25 Correct 563 ms 616 KB Guessed the password with 24228 queries.
26 Correct 405 ms 600 KB Guessed the password with 17468 queries.
27 Correct 613 ms 556 KB Guessed the password with 27851 queries.
28 Correct 363 ms 684 KB Guessed the password with 16178 queries.
29 Correct 671 ms 608 KB Guessed the password with 30025 queries.
30 Correct 385 ms 536 KB Guessed the password with 14075 queries.