#include <bits/stdc++.h>
using namespace std;
int query(string str);
string ans="";
vector<pair<int,int>> res;
void dnc(int l,int r,int num,char c,int n,int rside){
//printf("dnc %d %d %d %c %d:\n",l,r,num,c,n);
if(num==0)return;
if(l==r){
res.push_back({l,num});
return;
}
int m=((l+r)>>1)+1;
string tmp=ans;
tmp.resize(m);
tmp+=string(min(num,n-rside-m)+rside,c);
int qres=query(tmp)-m-rside;
//cout<<tmp<<' '<<qres<<endl;
int lnum=num-qres;
int rnum=qres;
tmp.clear();
dnc(l,m-1,lnum,c,n,rnum+rside);
dnc(m,r,rnum,c,n,rside);
}
string guess(int n,int s){
for(int i=0;i<s;++i){
char c='a'+i;
//printf("%c\n",c);
int num=query(string(n,c));
dnc(0,ans.length(),num,c,n,0);
int off=0;
for(auto[pos,num]:res){
ans.insert(pos+off,num,c);
off+=num;
}
res.clear();
//cout<<ans<<endl;
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Guessed the password with 56 queries. |
| 2 |
Correct |
2 ms |
208 KB |
Guessed the password with 101 queries. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Guessed the password with 23 queries. |
| 2 |
Correct |
1 ms |
208 KB |
Guessed the password with 56 queries. |
| 3 |
Correct |
1 ms |
208 KB |
Guessed the password with 11 queries. |
| 4 |
Correct |
2 ms |
208 KB |
Guessed the password with 93 queries. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
312 KB |
Guessed the password with 1377 queries. |
| 2 |
Correct |
15 ms |
320 KB |
Guessed the password with 1743 queries. |
| 3 |
Correct |
31 ms |
340 KB |
Guessed the password with 2838 queries. |
| 4 |
Correct |
47 ms |
348 KB |
Guessed the password with 4374 queries. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Guessed the password with 56 queries. |
| 2 |
Correct |
2 ms |
208 KB |
Guessed the password with 101 queries. |
| 3 |
Correct |
1 ms |
208 KB |
Guessed the password with 23 queries. |
| 4 |
Correct |
1 ms |
208 KB |
Guessed the password with 56 queries. |
| 5 |
Correct |
1 ms |
208 KB |
Guessed the password with 11 queries. |
| 6 |
Correct |
2 ms |
208 KB |
Guessed the password with 93 queries. |
| 7 |
Correct |
15 ms |
312 KB |
Guessed the password with 1377 queries. |
| 8 |
Correct |
15 ms |
320 KB |
Guessed the password with 1743 queries. |
| 9 |
Correct |
31 ms |
340 KB |
Guessed the password with 2838 queries. |
| 10 |
Correct |
47 ms |
348 KB |
Guessed the password with 4374 queries. |
| 11 |
Correct |
55 ms |
372 KB |
Guessed the password with 5236 queries. |
| 12 |
Correct |
32 ms |
380 KB |
Guessed the password with 4594 queries. |
| 13 |
Correct |
48 ms |
600 KB |
Guessed the password with 6674 queries. |
| 14 |
Correct |
66 ms |
396 KB |
Guessed the password with 6286 queries. |
| 15 |
Correct |
41 ms |
592 KB |
Guessed the password with 7048 queries. |
| 16 |
Correct |
74 ms |
404 KB |
Guessed the password with 6484 queries. |
| 17 |
Correct |
48 ms |
360 KB |
Guessed the password with 5989 queries. |
| 18 |
Correct |
29 ms |
336 KB |
Guessed the password with 5213 queries. |
| 19 |
Correct |
61 ms |
464 KB |
Guessed the password with 6188 queries. |
| 20 |
Correct |
56 ms |
380 KB |
Guessed the password with 5421 queries. |
| 21 |
Correct |
37 ms |
336 KB |
Guessed the password with 3751 queries. |
| 22 |
Correct |
36 ms |
372 KB |
Guessed the password with 3380 queries. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Guessed the password with 56 queries. |
| 2 |
Correct |
2 ms |
208 KB |
Guessed the password with 101 queries. |
| 3 |
Correct |
1 ms |
208 KB |
Guessed the password with 23 queries. |
| 4 |
Correct |
1 ms |
208 KB |
Guessed the password with 56 queries. |
| 5 |
Correct |
1 ms |
208 KB |
Guessed the password with 11 queries. |
| 6 |
Correct |
2 ms |
208 KB |
Guessed the password with 93 queries. |
| 7 |
Correct |
15 ms |
312 KB |
Guessed the password with 1377 queries. |
| 8 |
Correct |
15 ms |
320 KB |
Guessed the password with 1743 queries. |
| 9 |
Correct |
31 ms |
340 KB |
Guessed the password with 2838 queries. |
| 10 |
Correct |
47 ms |
348 KB |
Guessed the password with 4374 queries. |
| 11 |
Correct |
55 ms |
372 KB |
Guessed the password with 5236 queries. |
| 12 |
Correct |
32 ms |
380 KB |
Guessed the password with 4594 queries. |
| 13 |
Correct |
48 ms |
600 KB |
Guessed the password with 6674 queries. |
| 14 |
Correct |
66 ms |
396 KB |
Guessed the password with 6286 queries. |
| 15 |
Correct |
41 ms |
592 KB |
Guessed the password with 7048 queries. |
| 16 |
Correct |
74 ms |
404 KB |
Guessed the password with 6484 queries. |
| 17 |
Correct |
48 ms |
360 KB |
Guessed the password with 5989 queries. |
| 18 |
Correct |
29 ms |
336 KB |
Guessed the password with 5213 queries. |
| 19 |
Correct |
61 ms |
464 KB |
Guessed the password with 6188 queries. |
| 20 |
Correct |
56 ms |
380 KB |
Guessed the password with 5421 queries. |
| 21 |
Correct |
37 ms |
336 KB |
Guessed the password with 3751 queries. |
| 22 |
Correct |
36 ms |
372 KB |
Guessed the password with 3380 queries. |
| 23 |
Correct |
77 ms |
528 KB |
Guessed the password with 7770 queries. |
| 24 |
Correct |
67 ms |
592 KB |
Guessed the password with 6419 queries. |
| 25 |
Correct |
105 ms |
540 KB |
Guessed the password with 13653 queries. |
| 26 |
Correct |
93 ms |
544 KB |
Guessed the password with 10409 queries. |
| 27 |
Correct |
96 ms |
500 KB |
Guessed the password with 15732 queries. |
| 28 |
Correct |
93 ms |
432 KB |
Guessed the password with 9984 queries. |
| 29 |
Correct |
153 ms |
528 KB |
Guessed the password with 17065 queries. |
| 30 |
Correct |
70 ms |
568 KB |
Guessed the password with 8996 queries. |
