제출 #1208066

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1208066		Boomyday	Monster Game (JOI21_monster)	C++20	100 / 100	24 ms	436 KiB

monster

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

using ll = long long;
namespace {

bool example_variable;

}  // namespace


vector<int> merge(vector<int> l, vector<int> r){
    vector<int> res;
    int i = 0, j = 0;
    while (i < l.size() && j < r.size()){
        if (!Query(l[i], r[j])){
            res.push_back(l[i++]);
        } else {
            res.push_back(r[j++]);
        }
    }
    while (i < l.size()) res.push_back(l[i++]);
    while (j < r.size()) res.push_back(r[j++]);
    return res;
}

vector<int> merge_sort(vector<int>& T) {
    if (T.size() <= 1) return T;
    int mid = T.size() / 2;
    vector<int> left(T.begin(), T.begin() + mid);
    vector<int> right(T.begin() + mid, T.end());
    return merge(merge_sort(left), merge_sort(right));
}

std::vector<int> Solve(int N) {
  std::vector<int> T(N);
  for (int i = 0; i < N; i++) T[i] = i;
    T = merge_sort(T);



    vector<int> comp(N-1, 0);
    int ncp = 0;
    int gindex = -1;
    for(int i=max(N-15, 0);i<N-1;++i) {
        comp[i] = Query(T[i], T[N-1]); // 1 if T[i] is greater, 0 otherwise
        ncp += comp[i];
        if (comp[i]) gindex = i;
    }

    int findex = -1;
    if (ncp > 1){
        // findex is the index of the second 1 in comp
        bool onefound = false;
        for (int i = 0; i < N-1; i++) {
            if (comp[i] == 1) {
                if (onefound) {
                    findex = i;
                    break;
                } else {
                    onefound = true;
                }
            }
        }
    }
    else {
        if (gindex <= N-4){
            int cval = Query(T[gindex], T[N-2]);
            if (cval == 1) findex = N-1;
            else findex = N-2;
        }
        else{
            int s = 0;
            for(int i=max(N-15, 0);i<N-3;++i){
                s += Query(T[i], T[N-2]);
            }

            if (s > 0) {
                findex = N-1;
            }
            else {
                findex = N-2;
            }
        }
    }
    int pindex = N-1;
    while (findex >= 0){
        // reverse between findex and pindex
        reverse(T.begin() + findex, T.begin() + pindex + 1);
        if (findex == 0) break;
        int c = -1;
        for(int i=findex-1; i >= 0; --i) {
            int d = Query(T[i], T[findex]);
            if (d == 1) {
                c = i;
                break;
            }
        }
        pindex = findex - 1;
        findex = c;
    }
    vector<int> S(N);
    // S is the inverse of T
    for (int i = 0; i < N; i++) {
        S[T[i]] = i;
    }
    //output s
    /*
    for (int i = 0; i < N; i++) {
        cout << S[i] << " ";
    }
    cout << endl;*/
    return S;






}

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