oj.uz

Submission #239642

# Submission time Handle Problem Language Result Execution time Memory
239642 2020-06-17T00:49:48 Z luciocf Password (RMI18_password) C++14
80 / 100
 990 ms 760 KB 
#include <bits/stdc++.h>

using namespace std;

int query(string str);

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

string ans = "";

int qtd(int pos, char c)
{
	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 (query(aux) - (pos+1));
}

string guess(int n, int s)
{
	for (int i = 0; i < s; i++)
	{
		char c = (char)('a'+i);
		string aux = "";

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

		freq[i] = query(aux);
	}


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

		memset(nxt, 0, sizeof nxt);

		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;

			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:76: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 98 queries.
2 Correct 6 ms 384 KB Guessed the password with 180 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Guessed the password with 51 queries.
2 Correct 6 ms 384 KB Guessed the password with 122 queries.
3 Correct 5 ms 384 KB Guessed the password with 16 queries.
4 Correct 8 ms 384 KB Guessed the password with 270 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 384 KB Guessed the password with 4653 queries.
2 Correct 59 ms 384 KB Guessed the password with 4717 queries.
3 Correct 126 ms 384 KB Guessed the password with 10078 queries.
4 Correct 199 ms 392 KB Guessed the password with 13870 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Guessed the password with 98 queries.
2 Correct 6 ms 384 KB Guessed the password with 180 queries.
3 Correct 5 ms 384 KB Guessed the password with 51 queries.
4 Correct 6 ms 384 KB Guessed the password with 122 queries.
5 Correct 5 ms 384 KB Guessed the password with 16 queries.
6 Correct 8 ms 384 KB Guessed the password with 270 queries.
7 Correct 61 ms 384 KB Guessed the password with 4653 queries.
8 Correct 59 ms 384 KB Guessed the password with 4717 queries.
9 Correct 126 ms 384 KB Guessed the password with 10078 queries.
10 Correct 199 ms 392 KB Guessed the password with 13870 queries.
11 Correct 361 ms 428 KB Guessed the password with 18454 queries.
12 Correct 371 ms 384 KB Guessed the password with 20810 queries.
13 Correct 343 ms 384 KB Guessed the password with 20547 queries.
14 Correct 317 ms 384 KB Guessed the password with 21884 queries.
15 Correct 411 ms 384 KB Guessed the password with 23769 queries.
16 Correct 412 ms 396 KB Guessed the password with 25237 queries.
17 Correct 345 ms 384 KB Guessed the password with 20690 queries.
18 Correct 431 ms 384 KB Guessed the password with 22397 queries.
19 Correct 453 ms 556 KB Guessed the password with 22626 queries.
20 Correct 556 ms 504 KB Guessed the password with 25078 queries.
21 Correct 234 ms 504 KB Guessed the password with 11869 queries.
22 Correct 191 ms 504 KB Guessed the password with 11536 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Guessed the password with 98 queries.
2 Correct 6 ms 384 KB Guessed the password with 180 queries.
3 Correct 5 ms 384 KB Guessed the password with 51 queries.
4 Correct 6 ms 384 KB Guessed the password with 122 queries.
5 Correct 5 ms 384 KB Guessed the password with 16 queries.
6 Correct 8 ms 384 KB Guessed the password with 270 queries.
7 Correct 61 ms 384 KB Guessed the password with 4653 queries.
8 Correct 59 ms 384 KB Guessed the password with 4717 queries.
9 Correct 126 ms 384 KB Guessed the password with 10078 queries.
10 Correct 199 ms 392 KB Guessed the password with 13870 queries.
11 Correct 361 ms 428 KB Guessed the password with 18454 queries.
12 Correct 371 ms 384 KB Guessed the password with 20810 queries.
13 Correct 343 ms 384 KB Guessed the password with 20547 queries.
14 Correct 317 ms 384 KB Guessed the password with 21884 queries.
15 Correct 411 ms 384 KB Guessed the password with 23769 queries.
16 Correct 412 ms 396 KB Guessed the password with 25237 queries.
17 Correct 345 ms 384 KB Guessed the password with 20690 queries.
18 Correct 431 ms 384 KB Guessed the password with 22397 queries.
19 Correct 453 ms 556 KB Guessed the password with 22626 queries.
20 Correct 556 ms 504 KB Guessed the password with 25078 queries.
21 Correct 234 ms 504 KB Guessed the password with 11869 queries.
22 Correct 191 ms 504 KB Guessed the password with 11536 queries.
23 Correct 457 ms 624 KB Guessed the password with 23180 queries.
24 Correct 449 ms 644 KB Guessed the password with 20270 queries.
25 Correct 816 ms 628 KB Guessed the password with 41526 queries.
26 Correct 758 ms 544 KB Guessed the password with 35327 queries.
27 Correct 948 ms 448 KB Guessed the password with 46732 queries.
28 Correct 849 ms 424 KB Guessed the password with 38485 queries.
29 Incorrect 990 ms 760 KB Could not guess the password with 50000 queries.
30 Halted 0 ms 0 KB -