제출 #1240150

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

monster

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

#define all(a) (a).begin(), (a).end()
#define ll long long
#define ld long double
#define ui uint64_t
#define cont(set, element) ((set).find(element) != (set).end())

#define chmin(x, y) (x = min(x, y)) 
#define chmax(x, y) (x = max(x, y))

/********* DEBUG *********/

template <typename T>
void outvec(const vector<T>& Z){
    for (const T& x : Z)
    cout << x << ' ';
    cout << "\n";
}
void printVariable(const any& var) {
    if (!var.has_value()) {
        cout << "null";
        return;
    }

    if (var.type() == typeid(int)) {
        cout << any_cast<int>(var);
    } else if (var.type() == typeid(double)) {
        cout << any_cast<double>(var);
    } else if (var.type() == typeid(float)) {
        cout << any_cast<float>(var);
    } else if (var.type() == typeid(char)) {
        cout << any_cast<char>(var);
    } else if (var.type() == typeid(bool)) {
        cout << (any_cast<bool>(var) ? "true" : "false");
    } else if (var.type() == typeid(string)) {
        cout << any_cast<string>(var);
    } else if (var.type() == typeid(const char*)) {
        cout << any_cast<const char*>(var);
    } else if (var.type() == typeid(long long)) {
        cout << any_cast<long long>(var);
    } else {
        cout << "[unknown type]";
    }
}

template<typename... Args>
void outval(Args... args) {
    vector<any> variables = {args...};
    
    for (size_t i = 0; i < variables.size(); ++i) {
        printVariable(variables[i]);
        if (i != variables.size() - 1) {
            cout << " ";
        }
    }
    cout << "\n";
}

#define sp << " " <<
#define fi first
#define se second

/********* DEBUG *********/

const ll MOD = 1e9+7;
const ll MOD2 = 998244353;
const ll inf = 1e18;
const ll mxN = 100005;

vector<int> ans;

vector<int> msort(vector<int> curr){
    if (curr.size() == 1)
        return curr;

    ll m = curr.size() / 2;
    vector<int> a(curr.begin(), curr.begin() + m), b(curr.begin() + m, curr.end());

    a = msort(a);
    b = msort(b);

    int ap = 0, bp = 0;
    for (int i = 0; i < curr.size(); i++){
        if (ap == a.size()){
            curr[i] = b[bp++];
            continue;
        }

        if (bp == b.size()){
            curr[i] = a[ap++];
            continue;
        }
        
        if (Query(a[ap], b[bp]))
            curr[i] = b[bp++];
        else
            curr[i] = a[ap++];
    }

    return curr;
}

vector<int> Solve(int N) {
    ans.resize(N);
    iota(all(ans), 0);

    ans = msort(ans);
    //outvec(ans);
    vector<pair<ll,ll>> wins(min(N, 10));

    for (int i = 0; i < min(N, 10); i++){
        wins[i].second = ans[i];
        for (int j = i + 1; j < min(N, 10); j++){
            if (Query(ans[i], ans[j]))
                wins[i].first++;
            else
                wins[j].first++;
        }
    }

    sort(all(wins));
    ll back = wins[0].second;
    if (Query(wins[1].second, wins[0].second)) back = wins[1].second;
    //outval("b:",back);

    ans.erase(find(all(ans), back));
    ans.insert(ans.begin(), back);

    //outvec(ans);

    for (int i = 1; i < N; i++){
        int j = i;

        while (j < N && Query(ans[j], back))
            j++;

        reverse(ans.begin() + i, ans.begin() + min(j+1, N));
        i = j;
        back = ans[i];
    }


    vector<int> out(N);
    for (int i = 0; i < N; i++)
        out[ans[i]] = i;

    return out;
}

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