oj.uz

답안 #924763

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
924763 2024-02-09T16:03:50 Z boris_mihov Monster Game (JOI21_monster) C++17
0 / 100
 43 ms 444 KB 
#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[50];
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(200, n) ; ++i)
    {
        for (int j = i + 1 ; j < std::min(200, n) ; ++j)
        {
            if (Query(v[i], v[j])) cnt[i]++;
            else cnt[j]++;
        }
    }

    int min = 0;
    for (int i = 1 ; i < std::min(200, 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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 43 ms 444 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -