Submission #421124

#	Time	Username	Problem	Language	Result	Execution time	Memory
421124		Berted	Monster Game (JOI21_monster)	C++17	100 / 100	115 ms	4168 KiB

monster

#include "monster.h"
#include <random>
#include <iostream>
#include <algorithm>
#define vi vector<int>
#define uid uniform_int_distribution<int>

using namespace std;

/*
    Observations:
    - P_i will win against min(1, max(P_i, N - 2)) opponents.
    - Sorting with the comparator will give us an array such that it can be divided into 
      consecutive groups of [x, x - 1, ....], [y, y - 1, y - 2....], ...
    - There are no two consecutive groups of size 1
    - Each consecutive group's size is at most log N + 1.
*/

int done[1001][1001];

inline bool ask(int a, int b)
{
    bool ret = 0;
    if (a > b) {swap(a, b); ret = 1;}
    if (done[a][b] == -1) done[a][b] = Query(a, b);
    return ret ^ done[a][b];
}

int n, P[1001], A[1001];

inline void mergeSort(int L, int R)
{
    if (L < R)
    {
        int M = L + R >> 1;
        mergeSort(L, M);
        mergeSort(M + 1, R);
        for (int i = L; i <= R; i++) A[i] = P[i];
        int l = L, r = M + 1;
        for (int i = L; i <= R; i++)
        {
            if (l <= M && r <= R)
            {
                if (ask(A[r], A[l])) P[i] = A[l++];
                else P[i] = A[r++]; 
            }
            else if (l <= M) P[i] = A[l++];
            else P[i] = A[r++];
        }
    }
}

vector<int> Solve(int N) 
{
    vi ret(N); n = N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++) done[i][j] = -1;
        P[i] = i;
    }
    mergeSort(0, N - 1);

    int cnt = 0, prev = 1;
    for (int i = 2; i < 22 && i <= prev + 11 && i < N; i++)
    {
        if (ask(P[0], P[i])) {cnt++; prev = i;}
    }

    int cur;
    if (cnt > 1) {reverse(P, P + cnt + 1); cur = cnt;}
    else if (cnt == 1 && prev > 2)
    {
        if (ask(P[1], P[prev])) {cur = 0;}
        else {reverse(P, P + 2); cur = 1;}
    }
    else
    {
        int tp = 1;
        for (int i = 3; i < 14 && i < N; i++)
        {
            if (ask(P[1], P[i])) {tp = 0; break;}
        }
        reverse(P, P + tp + 1); cur = tp; 
    }

    for (int i = cur + 1; i < N; i++)
    {
        if (ask(P[cur], P[i]))
        {
            reverse(P + cur + 1, P + i + 1);
            cur = i;
        }
    }

    for (int i = 0; i < N; i++) ret[P[i]] = i;
    
    return ret;
}

Compilation message (stderr)

monster.cpp: In function 'void mergeSort(int, int)':
monster.cpp:35:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         int M = L + R >> 1;
      |                 ~~^~~

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