#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 |
2 ms |
200 KB |
Guessed the password with 108 queries. |
| 2 |
Correct |
3 ms |
200 KB |
Guessed the password with 236 queries. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
200 KB |
Guessed the password with 27 queries. |
| 2 |
Correct |
1 ms |
200 KB |
Guessed the password with 40 queries. |
| 3 |
Correct |
2 ms |
200 KB |
Guessed the password with 86 queries. |
| 4 |
Correct |
2 ms |
200 KB |
Guessed the password with 141 queries. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
67 ms |
440 KB |
Guessed the password with 6584 queries. |
| 2 |
Correct |
111 ms |
332 KB |
Guessed the password with 10389 queries. |
| 3 |
Correct |
190 ms |
352 KB |
Guessed the password with 14278 queries. |
| 4 |
Correct |
196 ms |
376 KB |
Guessed the password with 18700 queries. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
200 KB |
Guessed the password with 108 queries. |
| 2 |
Correct |
3 ms |
200 KB |
Guessed the password with 236 queries. |
| 3 |
Correct |
1 ms |
200 KB |
Guessed the password with 27 queries. |
| 4 |
Correct |
1 ms |
200 KB |
Guessed the password with 40 queries. |
| 5 |
Correct |
2 ms |
200 KB |
Guessed the password with 86 queries. |
| 6 |
Correct |
2 ms |
200 KB |
Guessed the password with 141 queries. |
| 7 |
Correct |
67 ms |
440 KB |
Guessed the password with 6584 queries. |
| 8 |
Correct |
111 ms |
332 KB |
Guessed the password with 10389 queries. |
| 9 |
Correct |
190 ms |
352 KB |
Guessed the password with 14278 queries. |
| 10 |
Correct |
196 ms |
376 KB |
Guessed the password with 18700 queries. |
| 11 |
Correct |
336 ms |
560 KB |
Guessed the password with 34810 queries. |
| 12 |
Correct |
450 ms |
804 KB |
Guessed the password with 33285 queries. |
| 13 |
Correct |
456 ms |
568 KB |
Guessed the password with 35543 queries. |
| 14 |
Correct |
366 ms |
672 KB |
Guessed the password with 37940 queries. |
| 15 |
Correct |
459 ms |
764 KB |
Guessed the password with 44827 queries. |
| 16 |
Correct |
400 ms |
640 KB |
Guessed the password with 40173 queries. |
| 17 |
Correct |
427 ms |
736 KB |
Guessed the password with 38668 queries. |
| 18 |
Correct |
547 ms |
880 KB |
Guessed the password with 47768 queries. |
| 19 |
Incorrect |
589 ms |
912 KB |
Could not guess the password with 50000 queries. |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
200 KB |
Guessed the password with 108 queries. |
| 2 |
Correct |
3 ms |
200 KB |
Guessed the password with 236 queries. |
| 3 |
Correct |
1 ms |
200 KB |
Guessed the password with 27 queries. |
| 4 |
Correct |
1 ms |
200 KB |
Guessed the password with 40 queries. |
| 5 |
Correct |
2 ms |
200 KB |
Guessed the password with 86 queries. |
| 6 |
Correct |
2 ms |
200 KB |
Guessed the password with 141 queries. |
| 7 |
Correct |
67 ms |
440 KB |
Guessed the password with 6584 queries. |
| 8 |
Correct |
111 ms |
332 KB |
Guessed the password with 10389 queries. |
| 9 |
Correct |
190 ms |
352 KB |
Guessed the password with 14278 queries. |
| 10 |
Correct |
196 ms |
376 KB |
Guessed the password with 18700 queries. |
| 11 |
Correct |
336 ms |
560 KB |
Guessed the password with 34810 queries. |
| 12 |
Correct |
450 ms |
804 KB |
Guessed the password with 33285 queries. |
| 13 |
Correct |
456 ms |
568 KB |
Guessed the password with 35543 queries. |
| 14 |
Correct |
366 ms |
672 KB |
Guessed the password with 37940 queries. |
| 15 |
Correct |
459 ms |
764 KB |
Guessed the password with 44827 queries. |
| 16 |
Correct |
400 ms |
640 KB |
Guessed the password with 40173 queries. |
| 17 |
Correct |
427 ms |
736 KB |
Guessed the password with 38668 queries. |
| 18 |
Correct |
547 ms |
880 KB |
Guessed the password with 47768 queries. |
| 19 |
Incorrect |
589 ms |
912 KB |
Could not guess the password with 50000 queries. |
| 20 |
Halted |
0 ms |
0 KB |
- |
