#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++)
~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
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. |
| # |
결과 |
실행 시간 |
메모리 |
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. |
| # |
결과 |
실행 시간 |
메모리 |
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. |
| # |
결과 |
실행 시간 |
메모리 |
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. |
| # |
결과 |
실행 시간 |
메모리 |
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. |
