Submission #1197431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197431		alexander707070	Monster Game (JOI21_monster)	C++20	82 / 100	34 ms	428 KiB

monster

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

using namespace std;

namespace monster{
    int n;
    int perm[MAXN],val[MAXN];
    bool flip[MAXN];

    void shift(int l,int r){
        for(int i=r+1;i>=l+1;i--){
            perm[i]=perm[i-1];
        }
    }
}

vector<int> Solve(int N){
    using namespace monster;

    n=N;
    perm[0]=0;

    for(int i=1;i<n;i++){
        
        if(Query(perm[0],i)){
            shift(0,i-1);
            perm[0]=i;
        }else if(Query(i,perm[i-1])){
            perm[i]=i;
        }else{
            int l=0,r=i-1,tt;

            while(l+1<r){
                tt=(l+r)/2;

                if(Query(perm[tt],i)){
                    r=tt;
                }else{
                    l=tt;
                }
            }

            shift(r,i-1);
            perm[r]=i;
        }
    }


    int last=0,br=0;

    vector<int> pos;
    for(int i=1;i<n;i++){
        if(Query(perm[0],perm[i])){
            br++; pos.push_back(perm[i]);
        }
    }

    if(br==n-2){
        int rb=0;
        for(int f=0;f<n-1;f++){
            if(Query(perm[n-1],perm[f]))rb++; 
        }

        if(rb==br)last=n-1;
        else last=n;    
    }else if(br>=2)last=br+1;
    else{
        int rb=0;
        for(int f=0;f<n;f++){
            if(f==pos[0])continue;
            if(Query(pos[0],f))rb++;   
        }

        if(rb==1)last=1;
        else last=2;
    }

    reverse(perm,perm+last);

    last--;
    for(int i=last+1;i<n;i++){
        if(Query(perm[last],perm[i])){
            reverse(perm+last+1,perm+i+1);
            last=i;
        }
    }

    for(int i=0;i<n;i++)val[perm[i]]=i;

    vector<int> sol;
    for(int i=0;i<n;i++)sol.push_back(val[i]);
    return sol;
}

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