#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
int query(string q);
vector<int> seen(26);
string alpha;
string go(const string& pre, int N, int S) {
if (S < 0) return "";
swap(alpha[S], alpha[rand() % (S + 1)]);
string q = pre + string(N - sz(pre), alpha[S]);
int cnt = query(q) - seen[alpha[S] - 'a'] - sz(pre);
//cerr << "pre " << pre << " S " << alpha[S] << " cnt " << cnt << endl;
string npre = pre + string(cnt, alpha[S]);
vector<string> tres;
for (int i = cnt; i >= 0; --i) {
tres.push_back(go(npre, N, S - 1));
npre.pop_back();
}
seen[alpha[S] - 'a'] += cnt;
string res;
for (int i = sz(tres) - 1; i >= 0; --i) {
res.insert(res.end(), all(tres[i]));
if (i) res.push_back(alpha[S]);
}
return res;
}
string guess(int N, int S) {
srand(time(NULL));
rep(i,0,S) alpha.push_back('a' + i);
return go("", N, S - 1);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
200 KB |
Guessed the password with 131 queries. |
| 2 |
Correct |
2 ms |
204 KB |
Guessed the password with 263 queries. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
296 KB |
Guessed the password with 29 queries. |
| 2 |
Correct |
1 ms |
200 KB |
Guessed the password with 55 queries. |
| 3 |
Correct |
3 ms |
300 KB |
Guessed the password with 162 queries. |
| 4 |
Correct |
2 ms |
200 KB |
Guessed the password with 183 queries. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
67 ms |
320 KB |
Guessed the password with 6215 queries. |
| 2 |
Correct |
70 ms |
456 KB |
Guessed the password with 8709 queries. |
| 3 |
Correct |
149 ms |
448 KB |
Guessed the password with 13977 queries. |
| 4 |
Correct |
182 ms |
616 KB |
Guessed the password with 19776 queries. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
200 KB |
Guessed the password with 131 queries. |
| 2 |
Correct |
2 ms |
204 KB |
Guessed the password with 263 queries. |
| 3 |
Correct |
1 ms |
296 KB |
Guessed the password with 29 queries. |
| 4 |
Correct |
1 ms |
200 KB |
Guessed the password with 55 queries. |
| 5 |
Correct |
3 ms |
300 KB |
Guessed the password with 162 queries. |
| 6 |
Correct |
2 ms |
200 KB |
Guessed the password with 183 queries. |
| 7 |
Correct |
67 ms |
320 KB |
Guessed the password with 6215 queries. |
| 8 |
Correct |
70 ms |
456 KB |
Guessed the password with 8709 queries. |
| 9 |
Correct |
149 ms |
448 KB |
Guessed the password with 13977 queries. |
| 10 |
Correct |
182 ms |
616 KB |
Guessed the password with 19776 queries. |
| 11 |
Correct |
499 ms |
612 KB |
Guessed the password with 39563 queries. |
| 12 |
Correct |
377 ms |
564 KB |
Guessed the password with 33569 queries. |
| 13 |
Correct |
454 ms |
696 KB |
Guessed the password with 40331 queries. |
| 14 |
Correct |
469 ms |
652 KB |
Guessed the password with 37268 queries. |
| 15 |
Correct |
296 ms |
764 KB |
Guessed the password with 34853 queries. |
| 16 |
Correct |
443 ms |
700 KB |
Guessed the password with 38480 queries. |
| 17 |
Correct |
377 ms |
596 KB |
Guessed the password with 38882 queries. |
| 18 |
Correct |
403 ms |
724 KB |
Guessed the password with 40323 queries. |
| 19 |
Correct |
527 ms |
864 KB |
Guessed the password with 42140 queries. |
| 20 |
Correct |
523 ms |
704 KB |
Guessed the password with 42551 queries. |
| 21 |
Correct |
541 ms |
784 KB |
Guessed the password with 40648 queries. |
| 22 |
Correct |
476 ms |
744 KB |
Guessed the password with 41731 queries. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
200 KB |
Guessed the password with 131 queries. |
| 2 |
Correct |
2 ms |
204 KB |
Guessed the password with 263 queries. |
| 3 |
Correct |
1 ms |
296 KB |
Guessed the password with 29 queries. |
| 4 |
Correct |
1 ms |
200 KB |
Guessed the password with 55 queries. |
| 5 |
Correct |
3 ms |
300 KB |
Guessed the password with 162 queries. |
| 6 |
Correct |
2 ms |
200 KB |
Guessed the password with 183 queries. |
| 7 |
Correct |
67 ms |
320 KB |
Guessed the password with 6215 queries. |
| 8 |
Correct |
70 ms |
456 KB |
Guessed the password with 8709 queries. |
| 9 |
Correct |
149 ms |
448 KB |
Guessed the password with 13977 queries. |
| 10 |
Correct |
182 ms |
616 KB |
Guessed the password with 19776 queries. |
| 11 |
Correct |
499 ms |
612 KB |
Guessed the password with 39563 queries. |
| 12 |
Correct |
377 ms |
564 KB |
Guessed the password with 33569 queries. |
| 13 |
Correct |
454 ms |
696 KB |
Guessed the password with 40331 queries. |
| 14 |
Correct |
469 ms |
652 KB |
Guessed the password with 37268 queries. |
| 15 |
Correct |
296 ms |
764 KB |
Guessed the password with 34853 queries. |
| 16 |
Correct |
443 ms |
700 KB |
Guessed the password with 38480 queries. |
| 17 |
Correct |
377 ms |
596 KB |
Guessed the password with 38882 queries. |
| 18 |
Correct |
403 ms |
724 KB |
Guessed the password with 40323 queries. |
| 19 |
Correct |
527 ms |
864 KB |
Guessed the password with 42140 queries. |
| 20 |
Correct |
523 ms |
704 KB |
Guessed the password with 42551 queries. |
| 21 |
Correct |
541 ms |
784 KB |
Guessed the password with 40648 queries. |
| 22 |
Correct |
476 ms |
744 KB |
Guessed the password with 41731 queries. |
| 23 |
Execution timed out |
629 ms |
708 KB |
Time limit exceeded (wall clock) |
| 24 |
Halted |
0 ms |
0 KB |
- |
