Submission #1159437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159437		brinton	Monster Game (JOI21_monster)	C++20	100 / 100	228 ms	420 KiB

monster

#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
namespace {

bool example_variable;

}  // namespace
bool ask(int a,int b){
    cerr << "? " << a << " " << b << endl;
    return Query(a,b);
}
void merge_sort(int l,int r,vector<int>& T){
    // terminate
    if(l == r){
        return;
    }
    // split
    int m =(l+r)/2;
    merge_sort(l,m,T);
    merge_sort(m+1,r,T);
    // combine;
    vector<int> cur;
    int a = l;
    int b = m+1;
    while(true){
        if(a == m+1 || b == r+1){
            // terminated;
            if(a == m+1){
                while(b != r+1){
                    cur.push_back(T[b]);
                    b++;
                }
            }else{
                while(a != m+1){
                    cur.push_back(T[a]);
                    a++;
                }
            }
            break;
        }
        if(ask(T[a],T[b])){
            cur.push_back(T[b]);
            b++;
        }else{
            cur.push_back(T[a]);
            a++;
        }
    }
    for(int i = 0;i < cur.size();i++){
        T[l+i] = cur[i];
    }
    cerr << l << " " << r << "(" << cur.size() << "):";
    for(int i = l;i <= r;i++)cerr << T[i] << " ";cerr << endl;

    return;
}
vector<int> Solve(int N) {
    vector<int> T(N);
    for(int i = 0;i < N;i++){
        T[i] = i;
    }
    merge_sort(0,N-1,T);
    // T is merge_sort
    for(auto i:T)cerr << i << " ";cerr << endl;
    // swap(T[N-1],T[N-2]);
    // for(int i = N-3;i >= 1;i--){
    //     if(!Query(T[i],T[i+1])){
    //         swap(T[i],T[i-1]);
    //     }
    // }
    /*
    TODO: we obtain a arr that T[a] < T[b] , but it may be a subsequence that reverse
    TODO: we are gonna check until T[a] > T[a+d] not hold (d > 1),and then reverse it
    TODO: to determine if need to swap last, we check T[a+d] and T[a+d-2]
    */
    for(int i = 0;i < N;){
        // i-1 is all good
        if(i == N-1)break;
        cerr << "start at: " << i << endl;
        for(auto i:T)cerr << i << " ";cerr << endl;
        int j = i+2;
        while(j < N && ask(T[i],T[j])){
            j++;
        }
        // reverse i~j-1 or i~j-2
        // if(j == N){
        //     // T[i] > T[j-1], swap all
        //     if(N-1 == i+2){
        //         // 3
        //     }else if(N-1 == i+3){

        //     }else{
        //         reverse(T.begin()+i,T.begin()+j-1+1);
        //     }
        // }else{
            if(j == i+2){
                /*
                cur i,i+1,i+2
                how to know rev(i,i+2) or (i,i+1)
                if(i != 0), we can check i-1,j-1
                case1: 0 2 1 4 3
                case2: 0 1 4 3 2

                is zero:
                case1: 1 0 3 2
                case2: 0 3 2 1
                */
                if(i != 0){
                    // finding the smallest(the one T[i-1] > T[i+1])
                    if(ask(T[i-1],T[i+1])){
                        reverse(T.begin()+i,T.begin()+i+1+1);
                    }else{
                        // not reverse
                        i = i+1;
                        continue;
                    }
                }else{
                    if(ask(T[i+1],T[i+3])){
                        // not reverse
                        i = i+1;
                        continue;
                    }else{
                        reverse(T.begin()+i,T.begin()+i+1+1);
                    }
                }
            }else if(j == i+3){
                /*
                cur i,i+1,i+2
                how to know rev(i,i+2) or (i,i+1)
                if(i != 0), we can check i-1,j-1
                case1: 0 3 2 1 5 4
                case1: 0 2 1 3 5 4
                case1: 0 1 3 2 5 4

                is zero:
                case1: 2 1 0 4 3
                case2: 1 0 2 4 3
                case3: 0 2 1 4 3
                               ^
                */
               if(i != 0){
                    // finding the smallest(the one T[i-1] > it)
                    if(ask(T[i-1],T[i+2])){
                        reverse(T.begin()+i,T.begin()+i+2+1);
                    }else if(ask(T[i-1],T[i+1])){
                        reverse(T.begin()+i,T.begin()+i+1+1);
                    }else{
                        reverse(T.begin()+i+1,T.begin()+j+1);
                    }
                }else{
                    int k = j+1;
                    while(ask(T[i],T[k]) == ask(T[i+1],T[k]) && ask(T[i+1],T[k]) == ask(T[i+2],T[k])) k++;
                    cerr << "3: " << i << " " << j << " " << k << endl;
                    // finding the biggest, the one > T[k];
                    if(ask(T[i],T[k])){
                        reverse(T.begin()+i,T.begin()+i+2+1);
                    }else if(ask(T[i+2],T[k])){
                        reverse(T.begin()+i,T.begin()+i+1+1);
                    }else{
                        reverse(T.begin()+i+1,T.begin()+i+2+1);
                    }


                    reverse(T.begin()+j,T.begin()+k+1);
                    i = k+1;
                    continue;
                }
            }else if(ask(T[j-1],T[j-3])){
                // if T[j-1] > T[j-3], j-1 is fake;
                reverse(T.begin()+i,T.begin()+j-2+1);
            }else{
                reverse(T.begin()+i,T.begin()+j-1+1);
            }
        // }
        i = j;
    }
    for(auto i:T)cerr << i << " ";cerr << endl;
    vector<int> ans(N);
    for(int i = 0;i < N;i++){
        ans[T[i]] = i;
    }
    return ans;
}
/*
testcase:
10
5 1 2 7 8 6 4 9 0 3 
10
0 9 1 8 2 7 3 6 4 5
7
0 1 2 3 4 5 6
7
0 2 4 6 1 3 5
*/

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