Submission #423526

#	Time	Username	Problem	Language	Result	Execution time	Memory
423526		79brue	Monster Game (JOI21_monster)	C++17	100 / 100	126 ms	328 KiB

monster

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

using namespace std;

typedef long long ll;

namespace {
    int n;
    int arr[1002];
    int arr2[1002];

    void Sort(int l, int r){
        if(l>=r) return;
        int m = (l+r)>>1;
        Sort(l, m);
        Sort(m+1, r);

        for(int i=l; i<=r; i++) arr2[i] = arr[i];
        for(int i=l, j=m+1, k=l; k<=r; k++){
            if(i==m+1) arr[k] = arr2[j++];
            else if(j==r+1) arr[k] = arr2[i++];
            else if(Query(arr2[i], arr2[j]) == 0) arr[k] = arr2[i++];
            else arr[k] = arr2[j++];
        }
    }

    void calculateElse(int tmp, int st){
        for(int i=st; i<n; i++){
            if(Query(arr[tmp], arr[i])){
                reverse(arr+tmp+1, arr+i+1);
                tmp = i;
            }
        }
    }

    void Reorder(int l, int r){
        if((r-l) <= 7){
            int cnt[1005] = {0};
            for(int i=l; i<=r; i++){
                for(int j=i+1; j<=r; j++){
                    if(Query(arr[i], arr[j])) cnt[arr[i]]++;
                    else cnt[arr[j]]++;
                }
            }
            sort(arr+l, arr+r+1, [&](int x, int y){
                return cnt[x] < cnt[y];
            });
            if(Query(arr[l], arr[l+1]) == 0) swap(arr[l], arr[l+1]);
            if(Query(arr[r], arr[r-1])) swap(arr[r], arr[r-1]);
            return;
        }

        int comp[1005] = {0};
        int cnt = 0;
        int lim = r;
        for(int i=l+1; i<=r; i++){
            if(Query(arr[l], arr[i])) comp[i] = 1, cnt++;
            if(comp[i-1] && !comp[i]){
                lim = i-1;
                break;
            }
        }
        if(cnt >= 2){ /// Case 1
            assert(lim >= l+3);
            if(Query(arr[lim], arr[lim-2])) reverse(arr+l, arr+lim);
            else reverse(arr+l, arr+lim+1);
            calculateElse(lim, lim+1);
            return;
        }
        else if(lim >= l+3){ /// Case 2
            if(Query(arr[l+1], arr[lim])) reverse(arr+l+1, arr+lim+1);
            else reverse(arr+l+2, arr+lim+1), swap(arr[l], arr[l+1]);
            calculateElse(lim, lim+1);
        }
        else if(lim==1){ /// Case 3
            Reorder(l+2, r);
        }
        else{ /// Case 4
            Reorder(l+3, r);
            if(Query(arr[l], arr[l+3])){
                reverse(arr+l, arr+l+3);
            }
            else if(Query(arr[l+1], arr[l+3])){
                swap(arr[l+1], arr[l+2]);
            }
            else{
                swap(arr[l], arr[l+1]);
            }
        }
    }
}

vector<int> Solve(int N){
    n = N;
    for(int i=0; i<n; i++) arr[i] = i;
    random_shuffle(arr, arr+n);
    Sort(0, n-1);

    Reorder(0, n-1);

//    for(int i=0; i<n; i++) printf("%d ", arr[i]);
//    puts("");

    vector<int> idx (n);
    for(int i=0; i<n; i++) idx[arr[i]] = i;
    return idx;
}

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