제출 #924756

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

monster

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

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

std::mt19937 rng(69420);
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 = 0;
    for (int i = 1 ; i < std::min(10, n) ; ++i)
    {
        if (cnt[i] == 1)
        {
            min = i;
        }
    }

    std::swap(v[0], v[min]);

    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: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75