oj.uz

Submission #239640

# Submission time Handle Problem Language Result Execution time Memory
239640 2020-06-17T00:04:45 Z luciocf Password (RMI18_password) C++14
80 / 100
 1071 ms 680 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;
		}

		while (true)
		{
			int ini = 0, fim = ans.size()-1, 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);
		}
	}

	return ans;
}

Compilation message

password.cpp: In function 'std::__cxx11::string guess(int, int)':
password.cpp:74: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 6 ms 384 KB Guessed the password with 111 queries.
2 Correct 7 ms 384 KB Guessed the password with 196 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Guessed the password with 68 queries.
2 Correct 6 ms 384 KB Guessed the password with 148 queries.
3 Correct 5 ms 384 KB Guessed the password with 16 queries.
4 Correct 9 ms 384 KB Guessed the password with 322 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 384 KB Guessed the password with 5434 queries.
2 Correct 92 ms 384 KB Guessed the password with 5621 queries.
3 Correct 191 ms 388 KB Guessed the password with 11336 queries.
4 Correct 285 ms 400 KB Guessed the password with 15291 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Guessed the password with 111 queries.
2 Correct 7 ms 384 KB Guessed the password with 196 queries.
3 Correct 5 ms 384 KB Guessed the password with 68 queries.
4 Correct 6 ms 384 KB Guessed the password with 148 queries.
5 Correct 5 ms 384 KB Guessed the password with 16 queries.
6 Correct 9 ms 384 KB Guessed the password with 322 queries.
7 Correct 88 ms 384 KB Guessed the password with 5434 queries.
8 Correct 92 ms 384 KB Guessed the password with 5621 queries.
9 Correct 191 ms 388 KB Guessed the password with 11336 queries.
10 Correct 285 ms 400 KB Guessed the password with 15291 queries.
11 Correct 391 ms 544 KB Guessed the password with 20396 queries.
12 Correct 348 ms 424 KB Guessed the password with 23042 queries.
13 Correct 415 ms 512 KB Guessed the password with 23157 queries.
14 Correct 400 ms 384 KB Guessed the password with 24602 queries.
15 Correct 574 ms 504 KB Guessed the password with 26469 queries.
16 Correct 562 ms 504 KB Guessed the password with 28297 queries.
17 Correct 424 ms 504 KB Guessed the password with 23612 queries.
18 Correct 481 ms 428 KB Guessed the password with 24968 queries.
19 Correct 550 ms 504 KB Guessed the password with 25137 queries.
20 Correct 550 ms 396 KB Guessed the password with 27772 queries.
21 Correct 274 ms 400 KB Guessed the password with 13535 queries.
22 Correct 251 ms 384 KB Guessed the password with 14074 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Guessed the password with 111 queries.
2 Correct 7 ms 384 KB Guessed the password with 196 queries.
3 Correct 5 ms 384 KB Guessed the password with 68 queries.
4 Correct 6 ms 384 KB Guessed the password with 148 queries.
5 Correct 5 ms 384 KB Guessed the password with 16 queries.
6 Correct 9 ms 384 KB Guessed the password with 322 queries.
7 Correct 88 ms 384 KB Guessed the password with 5434 queries.
8 Correct 92 ms 384 KB Guessed the password with 5621 queries.
9 Correct 191 ms 388 KB Guessed the password with 11336 queries.
10 Correct 285 ms 400 KB Guessed the password with 15291 queries.
11 Correct 391 ms 544 KB Guessed the password with 20396 queries.
12 Correct 348 ms 424 KB Guessed the password with 23042 queries.
13 Correct 415 ms 512 KB Guessed the password with 23157 queries.
14 Correct 400 ms 384 KB Guessed the password with 24602 queries.
15 Correct 574 ms 504 KB Guessed the password with 26469 queries.
16 Correct 562 ms 504 KB Guessed the password with 28297 queries.
17 Correct 424 ms 504 KB Guessed the password with 23612 queries.
18 Correct 481 ms 428 KB Guessed the password with 24968 queries.
19 Correct 550 ms 504 KB Guessed the password with 25137 queries.
20 Correct 550 ms 396 KB Guessed the password with 27772 queries.
21 Correct 274 ms 400 KB Guessed the password with 13535 queries.
22 Correct 251 ms 384 KB Guessed the password with 14074 queries.
23 Correct 559 ms 488 KB Guessed the password with 26370 queries.
24 Correct 512 ms 520 KB Guessed the password with 23692 queries.
25 Correct 1046 ms 496 KB Guessed the password with 46514 queries.
26 Correct 911 ms 680 KB Guessed the password with 40284 queries.
27 Incorrect 1071 ms 576 KB Could not guess the password with 50000 queries.
28 Halted 0 ms 0 KB -