#include <bits/stdc++.h>
using namespace std;
int query(string str);
string guess(int n,int s){
string res;
string qs;
vector<int> cnts(s);
for(int cc=0;cc<s;cc++){
char c=(char)('a'+cc);
qs.clear();
for(int i=0;i<n;i++)
qs.push_back(c);
int qres=query(qs);
cnts[cc]=qres;
}
vector<pair<int,int>> srt;
for(int i=0;i<s;i++)
srt.push_back(make_pair(cnts[i],i));
sort(begin(srt),end(srt),greater<pair<int,int>>());
for(int cc=0;cc<s;cc++){
char c=(char)('a'+srt[cc].second);
int maxcount=srt[cc].first;
qs.clear();
if(res.size()==0){
int qres=maxcount;
for(int i=0;i<qres;i++)
res.push_back(c);
}
else
if((int)res.size()<n){
int qres=maxcount;
if(qres==0)
continue;
vector<int> pos;
for(int l=1;l<=qres;l++){
int lo=0,hi=res.size();
while(lo<hi){
qs.clear();
int mid=(lo+hi)/2+1;
for(int i=0;i<mid;i++)
qs.push_back(res[i]);
for(int i=0;i<l;i++)
qs.push_back(c);
int smqres=query(qs);
if(smqres==(int)qs.size())
lo=mid;
else
hi=mid-1;
}
pos.push_back(lo);
}
reverse(begin(pos),end(pos));
string new_res;
for(int i=res.size();i>=0;i--){
while(pos.size()>0&&pos.back()>=i)
new_res.push_back(c),pos.pop_back();
if(i!=0)
new_res.push_back(res[i-1]);
}
reverse(begin(new_res),end(new_res));
res=new_res;
}
}
return res;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Guessed the password with 59 queries. |
| 2 |
Correct |
1 ms |
364 KB |
Guessed the password with 101 queries. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
364 KB |
Guessed the password with 116 queries. |
| 2 |
Correct |
1 ms |
364 KB |
Guessed the password with 132 queries. |
| 3 |
Correct |
1 ms |
364 KB |
Guessed the password with 75 queries. |
| 4 |
Correct |
4 ms |
364 KB |
Guessed the password with 337 queries. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
54 ms |
380 KB |
Guessed the password with 6927 queries. |
| 2 |
Correct |
90 ms |
380 KB |
Guessed the password with 10986 queries. |
| 3 |
Correct |
180 ms |
364 KB |
Guessed the password with 11895 queries. |
| 4 |
Correct |
263 ms |
364 KB |
Guessed the password with 17681 queries. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Guessed the password with 59 queries. |
| 2 |
Correct |
1 ms |
364 KB |
Guessed the password with 101 queries. |
| 3 |
Correct |
2 ms |
364 KB |
Guessed the password with 116 queries. |
| 4 |
Correct |
1 ms |
364 KB |
Guessed the password with 132 queries. |
| 5 |
Correct |
1 ms |
364 KB |
Guessed the password with 75 queries. |
| 6 |
Correct |
4 ms |
364 KB |
Guessed the password with 337 queries. |
| 7 |
Correct |
54 ms |
380 KB |
Guessed the password with 6927 queries. |
| 8 |
Correct |
90 ms |
380 KB |
Guessed the password with 10986 queries. |
| 9 |
Correct |
180 ms |
364 KB |
Guessed the password with 11895 queries. |
| 10 |
Correct |
263 ms |
364 KB |
Guessed the password with 17681 queries. |
| 11 |
Correct |
401 ms |
556 KB |
Guessed the password with 22729 queries. |
| 12 |
Correct |
350 ms |
540 KB |
Guessed the password with 22601 queries. |
| 13 |
Correct |
421 ms |
516 KB |
Guessed the password with 27496 queries. |
| 14 |
Correct |
467 ms |
424 KB |
Guessed the password with 27484 queries. |
| 15 |
Correct |
496 ms |
364 KB |
Guessed the password with 28381 queries. |
| 16 |
Correct |
494 ms |
420 KB |
Guessed the password with 28380 queries. |
| 17 |
Correct |
452 ms |
636 KB |
Guessed the password with 28220 queries. |
| 18 |
Correct |
499 ms |
492 KB |
Guessed the password with 28469 queries. |
| 19 |
Correct |
500 ms |
492 KB |
Guessed the password with 27687 queries. |
| 20 |
Correct |
479 ms |
548 KB |
Guessed the password with 27969 queries. |
| 21 |
Correct |
563 ms |
624 KB |
Guessed the password with 31261 queries. |
| 22 |
Correct |
640 ms |
420 KB |
Guessed the password with 31122 queries. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Guessed the password with 59 queries. |
| 2 |
Correct |
1 ms |
364 KB |
Guessed the password with 101 queries. |
| 3 |
Correct |
2 ms |
364 KB |
Guessed the password with 116 queries. |
| 4 |
Correct |
1 ms |
364 KB |
Guessed the password with 132 queries. |
| 5 |
Correct |
1 ms |
364 KB |
Guessed the password with 75 queries. |
| 6 |
Correct |
4 ms |
364 KB |
Guessed the password with 337 queries. |
| 7 |
Correct |
54 ms |
380 KB |
Guessed the password with 6927 queries. |
| 8 |
Correct |
90 ms |
380 KB |
Guessed the password with 10986 queries. |
| 9 |
Correct |
180 ms |
364 KB |
Guessed the password with 11895 queries. |
| 10 |
Correct |
263 ms |
364 KB |
Guessed the password with 17681 queries. |
| 11 |
Correct |
401 ms |
556 KB |
Guessed the password with 22729 queries. |
| 12 |
Correct |
350 ms |
540 KB |
Guessed the password with 22601 queries. |
| 13 |
Correct |
421 ms |
516 KB |
Guessed the password with 27496 queries. |
| 14 |
Correct |
467 ms |
424 KB |
Guessed the password with 27484 queries. |
| 15 |
Correct |
496 ms |
364 KB |
Guessed the password with 28381 queries. |
| 16 |
Correct |
494 ms |
420 KB |
Guessed the password with 28380 queries. |
| 17 |
Correct |
452 ms |
636 KB |
Guessed the password with 28220 queries. |
| 18 |
Correct |
499 ms |
492 KB |
Guessed the password with 28469 queries. |
| 19 |
Correct |
500 ms |
492 KB |
Guessed the password with 27687 queries. |
| 20 |
Correct |
479 ms |
548 KB |
Guessed the password with 27969 queries. |
| 21 |
Correct |
563 ms |
624 KB |
Guessed the password with 31261 queries. |
| 22 |
Correct |
640 ms |
420 KB |
Guessed the password with 31122 queries. |
| 23 |
Incorrect |
967 ms |
772 KB |
Could not guess the password with 50000 queries. |
| 24 |
Halted |
0 ms |
0 KB |
- |
