| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1132734 | vako_p | Password (RMI18_password) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define pb push_back
#define ll int
//int query(string str);
const int mxN = 1e5 + 5;
ll N,sz,cnt[mxN],cnt1[mxN];
string ss,s1;
pair<ll,ll> bins(char ch, ll l, ll r, ll val){
ll val1 = cnt[ch - 'a'];
while(r > l + 1){
ll mid = l + (r - l) / 2;
s1 = "";
if(mid > ss.size()) for(int i = 0; i >= 0; i++) i++;
for(int i = 0; i < mid; i++) s1 += ss[i];
ll szz = s1.size();
for(int i = 1; szz + i <= N; i++) s1 += ch;
ll ans = query(s1) - szz;
if(ans > val){
l = mid;
val1 = ans;
}
else r = mid;
}
return {l, val1};
}
string guess(int n, int sz1){
N = n;
sz = sz1;
for(int i = 0; i < sz; i++){
ss = "";
for(int j = 0; j < N; j++) ss += ('a' + i);
cnt[i] = query(ss);
}
ss = "";
for(int i = 0; i < cnt[0]; i++) ss += 'a';
for(int i = 1; i < sz; i++){
ll curr = 0;
ll l = 0, r = ss.size() + 1;
for(int i = 0; i <= N; i++) cnt1[i] = 0;
while(curr < cnt[i]){
pair<ll,ll> x = bins('a' + i, l, r, curr);
cnt1[x.first] = x.second - curr;
curr = x.second;
r = x.first;
}
s1 = "";
for(int i1 = ss.size(); i1 >= 0; i1--){
if(i1 < ss.size()) s1 += ss[i1];
for(int j = 0; j < cnt1[i1]; j++) s1 += ('a' + i);
}
reverse(s1.begin(), s1.end());
ss = s1;
}
return ss;
}