| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 287124 | crossing0ver | Traffickers (RMI18_traffickers) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
int m;
string suf,pref;
int query(string str);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<string> sub(27);
int par[27];
int PAR(int x) {
if (par[x] == x) return x;
return PAR(par[x]);
}
void removeF(string &s){
reverse(all(s));
if (s.size())
s.pop_back();
reverse(all(s));
return;
}
void join(int x,int y) {
x = PAR(x), y = PAR(y);
if (sub[x].size() > sub[y].size())
swap(x,y);
par[x] = y;
int tot = sub[x].size() + sub[y].size();
string pref;
int cur = sub[y].size();
for (int i = 0;pref.size() < tot && i < sub[x].size() ;i++) {
string P = pref + sub[x][i];
P += sub[y];
int F = query(P);
if (F > cur) {
pref += sub[x][i];
cur = F;
}else {
pref += sub[y][0];
removeF(sub[y]);
i--;
}
}
sub[y] = pref;
}
string guess(int n, int s) {
string pref,P;
for (int i = 0;i < 26; i++) {
par[i] = i;
for (int j = 0; j < n; j++)
P+='a'+ i;
int x = query(P);
P.clear();
for (int j = 0; j < 26; j++)
P+='a' + i;
sub[i] = P;
P.clear();
}
for (int i = 1; i < 26; i++) {
join(i,1);
}
int x = PAR(0);
return sub[x];
vector<char> D;
for (char i = 'a'; i < 'a' + s ; i++)
D.pb(i);
shuffle(all(D),rng);
map<char,int> mp;
for (int i = 0;i < s; i++) mp[D[i]] = i;
char fs = 'a';
for (; pref.size() + suf.size() < n; ) {
int len = suf.size() + pref.size();
char LAST = ((int)pref.size() ? pref.back() : 'a');
int cur = len;
// vector<char> D = T;
for (int z = 1; z + pref.size() + suf.size() <= n;) {
bool flag = 0;
vector<char> Q;
// shuffle(D.begin(),D.end(),rng);
for (int b= max((pref.size() ? mp[pref.back()] : 0),(suf.size() ? mp[suf[0]] : 0)); b < s; b++){
char c = D[b];
/// for (char c : D) {
P = pref + c;
P += suf;
int F = query(P);
if (F > cur) {
LAST = c;
pref += c;
cur = F;
flag = 1;
break;
}
// else Q.pb(c);
}
// for (char c : Q) D.erase(find(all(D),c));
if (flag == 0) break;
}
reverse(all(suf));
if (pref.size())
suf+=pref.back();
reverse(all(suf));
if (pref.size())
pref.pop_back();
if (pref.size() + suf.size() == n) {
pref += suf;
int Z = query(pref);
return pref;
}
}
pref += suf;
int z = query(pref);
return pref;
}
/*
main() {
ios::sync_with_stdio(0);
cin.tie(0);
}*/