oj.uz

Submission #239643

# Submission time Handle Problem Language Result Execution time Memory
239643 2020-06-17T01:30:46 Z luciocf Password (RMI18_password) C++14
100 / 100
 753 ms 680 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)
{
	srand(time(0));
	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];
	}

	vector<int> V;

	for (int i = 0; i < s; i++)
		V.push_back(i);

	random_shuffle(V.begin(), V.end());

	for (auto i: V)
	{
		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:93: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 66 queries.
2 Correct 5 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 5 ms 412 KB Guessed the password with 47 queries.
3 Correct 5 ms 384 KB Guessed the password with 18 queries.
4 Correct 6 ms 384 KB Guessed the password with 97 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 384 KB Guessed the password with 2050 queries.
2 Correct 38 ms 384 KB Guessed the password with 2633 queries.
3 Correct 69 ms 384 KB Guessed the password with 4400 queries.
4 Correct 105 ms 412 KB Guessed the password with 6985 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Guessed the password with 66 queries.
2 Correct 5 ms 384 KB Guessed the password with 109 queries.
3 Correct 5 ms 384 KB Guessed the password with 20 queries.
4 Correct 5 ms 412 KB Guessed the password with 47 queries.
5 Correct 5 ms 384 KB Guessed the password with 18 queries.
6 Correct 6 ms 384 KB Guessed the password with 97 queries.
7 Correct 32 ms 384 KB Guessed the password with 2050 queries.
8 Correct 38 ms 384 KB Guessed the password with 2633 queries.
9 Correct 69 ms 384 KB Guessed the password with 4400 queries.
10 Correct 105 ms 412 KB Guessed the password with 6985 queries.
11 Correct 126 ms 384 KB Guessed the password with 7143 queries.
12 Correct 140 ms 384 KB Guessed the password with 7514 queries.
13 Correct 177 ms 504 KB Guessed the password with 10593 queries.
14 Correct 188 ms 632 KB Guessed the password with 10767 queries.
15 Correct 225 ms 384 KB Guessed the password with 10334 queries.
16 Correct 214 ms 504 KB Guessed the password with 10821 queries.
17 Correct 174 ms 384 KB Guessed the password with 9397 queries.
18 Correct 176 ms 384 KB Guessed the password with 8951 queries.
19 Correct 193 ms 384 KB Guessed the password with 9419 queries.
20 Correct 200 ms 388 KB Guessed the password with 9641 queries.
21 Correct 115 ms 556 KB Guessed the password with 5775 queries.
22 Correct 118 ms 384 KB Guessed the password with 5984 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Guessed the password with 66 queries.
2 Correct 5 ms 384 KB Guessed the password with 109 queries.
3 Correct 5 ms 384 KB Guessed the password with 20 queries.
4 Correct 5 ms 412 KB Guessed the password with 47 queries.
5 Correct 5 ms 384 KB Guessed the password with 18 queries.
6 Correct 6 ms 384 KB Guessed the password with 97 queries.
7 Correct 32 ms 384 KB Guessed the password with 2050 queries.
8 Correct 38 ms 384 KB Guessed the password with 2633 queries.
9 Correct 69 ms 384 KB Guessed the password with 4400 queries.
10 Correct 105 ms 412 KB Guessed the password with 6985 queries.
11 Correct 126 ms 384 KB Guessed the password with 7143 queries.
12 Correct 140 ms 384 KB Guessed the password with 7514 queries.
13 Correct 177 ms 504 KB Guessed the password with 10593 queries.
14 Correct 188 ms 632 KB Guessed the password with 10767 queries.
15 Correct 225 ms 384 KB Guessed the password with 10334 queries.
16 Correct 214 ms 504 KB Guessed the password with 10821 queries.
17 Correct 174 ms 384 KB Guessed the password with 9397 queries.
18 Correct 176 ms 384 KB Guessed the password with 8951 queries.
19 Correct 193 ms 384 KB Guessed the password with 9419 queries.
20 Correct 200 ms 388 KB Guessed the password with 9641 queries.
21 Correct 115 ms 556 KB Guessed the password with 5775 queries.
22 Correct 118 ms 384 KB Guessed the password with 5984 queries.
23 Correct 284 ms 444 KB Guessed the password with 14090 queries.
24 Correct 235 ms 440 KB Guessed the password with 11232 queries.
25 Correct 537 ms 548 KB Guessed the password with 24292 queries.
26 Correct 391 ms 636 KB Guessed the password with 17947 queries.
27 Correct 589 ms 560 KB Guessed the password with 27867 queries.
28 Correct 394 ms 524 KB Guessed the password with 16548 queries.
29 Correct 753 ms 680 KB Guessed the password with 30272 queries.
30 Correct 298 ms 572 KB Guessed the password with 12079 queries.