| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1147797 | guagua0407 | Monster Game (JOI21_monster) | C++20 | 0 ms | 0 KiB |
#include "monster.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
namespace {
vector<int> ans;
mt19937 rng(time(NULL));
vector<int> res;
} // namespace
void go(int l,int r,vector<int> a,int LL=-1,int RR=-1){
/*cout<<l<<' '<<r<<' '<<LL<<' '<<RR<<'\n';
for(auto v:a){
cout<<v<<' ';
}
cout<<'\n';*/
assert(r-l+1==(int)a.size());
if(r<l) return;
if(l==r){
ans[a[0]]=l;
return;
}
if(r-l==1){
int cur=Query(a[0],a[1]);
if(cur==1){
ans[a[0]]=l;
ans[a[1]]=r;
}
else{
ans[a[0]]=r;
ans[a[1]]=l;
}
return;
}
if(r-l==2){
assert(LL!=-1 or RR!=-1);
if(LL!=-1){
pair<int,int> b={-1,-1};
int bad;
for(int i=0;i<3;i++){
if(Query(LL,a[i])){
ans[a[i]]=l;
bad=i;
break;
}
}
for(int i=0;i<3;i++){
if(i!=bad){
if(b.f==-1) b.f=a[i];
else b.s=a[i];
}
}
if(Query(b.f,b.s)){
ans[b.f]=l+1;
ans[b.s]=l+2;
}
else{
ans[b.f]=l+2;
ans[b.s]=l+1;
}
}
else{
pair<int,int> b={-1,-1};
int bad;
for(int i=0;i<3;i++){
if(Query(a[i],RR)){
ans[a[i]]=r;
bad=i;
break;
}
}
for(int i=0;i<3;i++){
if(i!=bad){
if(b.f==-1) b.f=a[i];
else b.s=a[i];
}
}
if(Query(b.f,b.s)){
ans[b.f]=l;
ans[b.s]=l+1;
}
else{
ans[b.f]=l+1;
ans[b.s]=l;
}
}
return;
}
int sz=(int)a.size();
int mid=abs((int)rng())%sz;
swap(a[0],a[mid]);
vector<int> prv,nxt;
for(int i=1;i<sz;i++){
if(Query(a[0],a[i])==1) prv.push_back(a[i]);
else nxt.push_back(a[i]);
}
if((int)prv.size()==1){
//cout<<"first"<<'\n';
int cnt=0;
vector<int> cand;
bool tf=false;
for(auto v:nxt){
if(Query(prv[0],v)){
cnt++;
cand.push_back(v);
}
if(cnt>=2){
tf=true;
break;
}
}
if(!tf){
assert((int)cand.size()==1);
ans[a[0]]=l;
ans[prv[0]]=l+1;
ans[cand[0]]=l+2;
vector<int> R;
for(auto v:nxt){
if(v!=cand[0]){
R.push_back(v);
}
}
go(l+3,r,R,cand[0],RR);
}
else{
assert((int)cand.size()==2);
ans[a[0]]=l+1;
ans[prv[0]]=l+2;
if(Query(cand[0],cand[1])) swap(cand[0],cand[1]);
ans[cand[0]]=l;
ans[cand[1]]=l+3;
vector<int> R;
for(auto v:nxt){
if(v!=cand[0] and v!=cand[1]){
R.push_back(v);
}
}
go(l+4,r,R,cand[1],RR);
}
}
else if((int)nxt.size()==1){
//cout<<"second"<<'\n';
int cnt=0;
vector<int> cand;
bool tf=false;
for(auto v:prv){
if(!Query(nxt[0],v)){
cnt++;
cand.push_back(v);
}
if(cnt>=2){
tf=true;
break;
}
}
if(!tf){
assert((int)cand.size()==1);
ans[a[0]]=r;
ans[nxt[0]]=r-1;
ans[cand[0]]=r-2;
vector<int> L;
for(auto v:prv){
if(v!=cand[0]){
L.push_back(v);
}
}
go(l,r-3,L,LL,cand[0]);
}
else{
assert((int)cand.size()==2);
ans[a[0]]=r-1;
ans[nxt[0]]=r-2;
if(Query(cand[0],cand[1])) swap(cand[0],cand[1]);
ans[cand[0]]=r-3;
ans[cand[1]]=r;
vector<int> L;
for(auto v:prv){
if(v!=cand[0] and v!=cand[1]){
L.push_back(v);
}
}
go(l,r-4,L,LL,cand[0]);
}
}
else{
//cout<<"third"<<'\n';
for(int i=1;i<(int)prv.size();i++){
if(Query(prv[i],prv[0])) swap(prv[0],prv[i]);
}
for(int i=1;i<(int)nxt.size();i++){
if(!Query(nxt[i],nxt[0])) swap(nxt[0],nxt[i]);
}
ans[a[0]]=l+(int)prv.size();
int pp=prv[0];
int nn=nxt[0];
ans[prv[0]]=ans[a[0]]+1;
ans[nxt[0]]=ans[a[0]]-1;
reverse(all(prv));
reverse(all(nxt));
prv.pop_back();
nxt.pop_back();
go(l,ans[a[0]]-2,prv,LL,nn);
go(ans[a[0]]+2,r,nxt,pp,RR);
}
}
std::vector<int> Solve(int n) {
vector<int> a(n);
ans=vector<int>(n,-1);
res.resize(n);
for(int i=0;i<n;i++){
a[i]=i;
}
shuffle(all(a),rng());
go(0,n-1,a);
return ans;
}