Submission #1159335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159335		brinton	Monster Game (JOI21_monster)	C++20	0 / 100	39 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;){
        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
            reverse(T.begin()+i,T.begin()+j-1+1);
        }else{
            if(j == i+2){
                // must swap;
                reverse(T.begin()+i,T.begin()+j-1+1);
            }else if(ask(T[j],T[j-2])){
                // if T[j] > T[j-2], 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;
}

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