oj.uz

Submission #924761

# Submission time Handle Problem Language Result Execution time Memory
924761 2024-02-09T16:03:31 Z boris_mihov Monster Game (JOI21_monster) C++17
0 / 100
 61 ms 592 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(50, n) ; ++i)
    {
        for (int j = i + 1 ; j < std::min(50, n) ; ++j)
        {
            if (Query(v[i], v[j])) cnt[i]++;
            else cnt[j]++;
        }
    }

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

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Partially correct 51 ms 424 KB Partially correct
2 Partially correct 61 ms 428 KB Partially correct
3 Partially correct 52 ms 440 KB Partially correct
4 Partially correct 58 ms 428 KB Partially correct
5 Partially correct 38 ms 592 KB Partially correct
6 Correct 55 ms 424 KB Output is correct
7 Correct 36 ms 424 KB Output is correct
8 Partially correct 48 ms 428 KB Partially correct
9 Incorrect 51 ms 420 KB Wrong Answer [3]
10 Halted 0 ms 0 KB -