제출 #924774

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
924774		boris_mihov	Monster Game (JOI21_monster)	C++17	100 / 100	67 ms	600 KiB

monster

#include "monster.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <chrono>
#include <random>

typedef long long llong;
const int MAXN = 1000 + 10;
const int INF  = 1e9;

std::mt19937 rng(15); //std::chrono::steady_clock::now().time_since_epoch().count());
std::vector <int> v;
std::vector <int> res;

void rec(int l, int r)
{
    if (l == r)
    {
        return;
    }   

    int mid = (l + r) / 2;
    rec(l, mid);
    rec(mid + 1, r);

    int ptr = l;
    int lPtr = l, rPtr = mid + 1;
    while (lPtr <= mid || rPtr <= r)
    {
        if (lPtr == mid + 1)
        {
            res[ptr++] = v[rPtr++];
            continue;
        }

        if (rPtr == r + 1)
        {
            res[ptr++] = v[lPtr++];
            continue;
        }

        if (Query(v[rPtr], v[lPtr]))
        {
            res[ptr++] = v[lPtr++];
        } else
        {
            res[ptr++] = v[rPtr++];
        }
    }

    for (int i = l ; i <= r ; ++i)
    {
        v[i] = res[i];
    }
}

int cnt[10];
std::vector <int> Solve(int n) 
{
    v.resize(n);
    res.resize(n);
    std::iota(v.begin(), v.end(), 0);
    std::shuffle(v.begin(), v.end(), rng);
    rec(0, n - 1);

    for (int i = 0 ; i < std::min(10, n) ; ++i)
    {
        for (int j = i + 1 ; j < std::min(10, n) ; ++j)
        {
            if (Query(v[i], v[j])) cnt[i]++;
            else cnt[j]++;
        }
    }

    int min = -1;
    for (int i = 0 ; i < std::min(10, n) ; ++i)
    {
        if (cnt[i] == 1)
        {
            if (min == -1 || Query(v[i], v[min])) min = i;
        }
    }

    if (min != 0)
    {
        int beg = v[0];
        int zero = v[min];
        v.erase(v.begin() + min);
        v.erase(v.begin());
        v.insert(v.begin(), zero);
        v.insert(v.begin() + min, beg);
    }

    int idx = 0;
    for (int i = 1 ; i < n ; ++i)
    {
        if (Query(v[idx], v[i]))
        {
            std::reverse(v.begin() + idx + 1, v.begin() + i + 1);
            idx = i;
        }
    }
    
    for (int i = 0 ; i < n ; ++i)
    {
        res[v[i]] = i;
    }

    return res;
}

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