Submission #891321

#	Time	Username	Problem	Language	Result	Execution time	Memory
891321		SorahISA	Monster Game (JOI21_monster)	C++17	0 / 100	15 ms	600 KiB

monster

#ifndef SorahISA
#define SorahISA
#include SorahISA __FILE__ SorahISA

namespace {

mt19937_64 rng(880301);

} /// end of unnamed namespace

vector<int> solve_small(int N, vector<int> id) {
    vector<int> S(N);
    vector<int> win(N, 0);
    
    for (int i = 0; i < N; ++i) {
        for (int j = i+1; j < N; ++j) ++win[Query(id[i], id[j]) ? i : j];
    }
    
    vector<int> weak, strong;
    for (int i = 0; i < N; ++i) {
        if (win[i] == 1) weak.eb(i);
        if (win[i] == N-2) strong.eb(i);
        if (1 < win[i] and win[i] < N-2) S[i] = win[i];
    }
    
    if (Query(id[weak[0]], id[weak[1]])) S[weak[0]] = 0, S[weak[1]] = 1;
    else                                 S[weak[0]] = 1, S[weak[1]] = 0;
    
    if (Query(id[strong[0]], id[strong[1]])) S[strong[0]] = N-2, S[strong[1]] = N-1;
    else                                     S[strong[0]] = N-1, S[strong[1]] = N-2;
    
    return S;
}

vector<int> solve_large(int N, vector<int> id) {
    vector<int> S(N);
    
    function<void(int, int, vector<int>&)> recur = [&](int L, int R, vector<int> &vec) {
        int n = R - L + 1;
        if (n <= 10) {
            auto _S = solve_small(n, vec);
            for (int i = 0; i < n; ++i) S[vec[i]] = _S[i] + L;
            return;
        }
        
        vector<int> lo, hi;
        while (true) {
            lo.clear(), hi.clear();
            int pos = rng() % n; swap(vec[0], vec[pos]);
            for (int i = 1; i < n; ++i) {
                (Query(vec[0], vec[i]) ? lo : hi).eb(vec[i]);
            }
            if (SZ(lo) > 1 and SZ(hi) > 1) { S[vec[0]] = L + SZ(lo); break; }
        }
        
        int lo_mx = 0, hi_mn = 0;
        for (int i = 1; i < SZ(lo); ++i) { if (Query(lo[i], lo[lo_mx])) lo_mx = i; }
        for (int i = 1; i < SZ(hi); ++i) { if (Query(hi[hi_mn], hi[i])) hi_mn = i; }
        swap(lo[lo_mx], hi[hi_mn]);
        
        // debug(L, R, vec);
        // debug(lo);
        // debug(hi);
        
        int M = L + SZ(lo);
        recur(L, M-1, lo);
        recur(M+1, R, hi);
    };
    
    recur(0, N-1, id);
    
    return S;
}

vector<int> Solve(int N) {
    vector<int> id(N); iota(ALL(id), 0);
    return solve_large(N, id);
}

#else

#ifdef local
#include "C/monster.h"
#else
#include "monster.h"
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;
// #define int int64
using float80 = long double;
// #define double float80
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;

#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())

template <typename T>
ostream & operator << (ostream &os, const vector<T> &vec) {
    os << "[";
    for (int i = 0; i < SZ(vec); ++i) {
        if (i) os << ", ";
        os << vec[i];
    }
    os << "]";
    return os;
}

#ifdef local
#define fastIO() void()
#define debug(...) \
    fprintf(stderr, "\u001b[33m"), \
    fprintf(stderr, "At [%s], line %d: (%s) = ", __FUNCTION__, __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), \
    fprintf(stderr, "\u001b[0m")
template <typename T> void _do(T &&_t) { cerr << _t << "\n"; }
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) { cerr << _t << ", ", _do(_u...); }
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#endif

template <typename T, typename U> bool chmin(T &lhs, U rhs) { return lhs > rhs ? lhs = rhs, 1 : 0; }
template <typename T, typename U> bool chmax(T &lhs, U rhs) { return lhs < rhs ? lhs = rhs, 1 : 0; }

#endif

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