제출 #1147789

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147789		guagua0407	Monster Game (JOI21_monster)	C++20	0 / 100	6 ms	436 KiB

monster

#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){
    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){
        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){
        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{
        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();
        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,nxt[0]);
        go(ans[a[0]]+2,r,nxt,prv[0],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;
    }
    go(0,n-1,a);
    return ans;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75