Submission #1157465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157465		alexander707070	Monster Game (JOI21_monster)	C++20	10 / 100	62 ms	4420 KiB

monster

#include<bits/stdc++.h>
#define MAXN 1007
#include "monster.h"

using namespace std;

namespace {

    bool example_variable;
    int n;
}  // namespace

int compared[MAXN][MAXN];
int deg[MAXN];

int value[MAXN];

int ask(int x,int y){
    if(compared[x][y]!=0)return compared[x][y];

    compared[x][y]=1+Query(x,y);
    compared[y][x]=3-compared[x][y];

    return compared[x][y];
}

bool cmp(int x,int y){
    if(deg[x]!=deg[y])return deg[x]<deg[y];
    return ask(x,y)==2;
}

bool cmp2(int x,int y){
    return value[x]<value[y];
}

void dumb(int l,int r,vector<int> v){
    for(int i:v)deg[i]=0;

    for(int i=0;i<v.size();i++){
        for(int f=i+1;f<v.size();f++){
            if(ask(v[i],v[f])==2)deg[v[i]]++;
            else deg[v[f]]++;
        }
    }

    sort(v.begin(),v.end(),cmp);

    for(int i=0;i<v.size();i++){
        value[v[i]]=l+i;
    }
}

int biggest(vector<int> v){
    int curr=v[0];
    for(int i=1;i<v.size();i++){
        if(ask(v[i],curr)==2)curr=v[i];
    }

    return curr;
}

void find_triple(vector<int> v,int &p1,int &p2,int &p3){
    p1=v[0]; p2=v[1]; p3=-1;

    if(ask(p1,p2)==1)swap(p1,p2);

    vector<int> small,big;
    for(int i=2;i<v.size();i++){
        if(ask(p2,v[i])==2 and ask(v[i],p1)==2){
            p3=v[i]; break;
        }

        if(ask(p2,v[i])==2 and ask(p1,v[i])==2){
            small.push_back(v[i]);
        }
    }
    
    if(p3==-1){
        p1=biggest(small);

        for(int i=0;i<v.size();i++){
            if(v[i]==p1 or v[i]==p2)continue;
            
            if(ask(p1,v[i])==2 and ask(v[i],p2)==2){
                p3=v[i]; break;
            }
        }
    }
}

void solve(int l,int r,vector<int> v){

    if(v.empty())return;

    if(r-l+1<=4){
        dumb(l,r,v);
        return;
    }else{

        random_shuffle(v.begin(),v.end());
        
        int p1,p2,p3,p4=-1,pivot;
        find_triple(v,p1,p2,p3);

        vector<int> ll,rr;

        for(int i=0;i<v.size();i++){
            if(v[i]==p1 or v[i]==p2 or v[i]==p3)continue;

            if(ask(p1,v[i])==1 and ask(p2,v[i])==1 and ask(p3,v[i])==1){
                rr.push_back(v[i]); continue;
            }

            if(ask(p1,v[i])==2 and ask(p2,v[i])==2 and ask(p3,v[i])==2){
                ll.push_back(v[i]); continue;
            }


            if(p4==-1)p4=v[i];
            else{
                int sum=ask(p1,v[i]) + ask(p2,v[i]) + ask(p3,v[i]);
                if(sum==4)rr.push_back(v[i]);
                else ll.push_back(v[i]);
            }
        }

        dumb(0,3,{p1,p2,p3,p4});
        if(value[p1]>=1 and value[p1]<=2)pivot=p1;
        if(value[p2]>=1 and value[p2]<=2)pivot=p2;
        if(value[p3]>=1 and value[p3]<=2)pivot=p3;

        int sz=l+int(ll.size());
        value[p1]+=sz; value[p2]+=sz; value[p3]+=sz; value[p4]+=sz;

        vector<int> sp={p1,p2,p3,p4};
        sort(sp.begin(),sp.end(),cmp2);

        if(!ll.empty()){
            int pt=0;
            while(ll.size()<4){
                ll.push_back(sp[pt]); pt++;
            }

            solve(l,l+int(ll.size())-1,ll);
        }

        if(!rr.empty()){
            int pt=3;
            while(rr.size()<4){
                rr.push_back(sp[pt]); pt--;
            }

            solve(r-int(rr.size())+1,r,rr);
        }
    }
}

vector<int> Solve(int N){
    n=N;

    vector<int> v,ans;
    for(int i=0;i<n;i++)v.push_back(i);
    solve(0,n-1,v);

    for(int i=0;i<n;i++){
        ans.push_back(value[i]);
    }

    return ans;
}

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