Submission #1236187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236187		countless	Monster Game (JOI21_monster)	C++20	10 / 100	58 ms	424 KiB

monster

#include "monster.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

const ll MOD = 998244353;
const ll INF = 1e18;
const ld EPS = 1e-12;

#define endl "\n"
#define sp <<" "<<
#define REP(i, a, b) for(ll i = a; i < b; i++)
#define dbg(x) cout << #x << " = " << x << endl
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

template <typename Key, typename Value>
using hash_map = unordered_map<Key, Value, custom_hash>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// uniform_int_distribution<int>(a, b)(rng);
// shuffle(all(a), rng);

namespace {
    bool example_variable;
}

vector<int> ans;

void work(int l, int r) {
    if (l == r) return;

    int m = (l+r) / 2;

    work(l, m);
    work(m+1, r);

    vector<int> left, right, temp;
    for (int i = l; i <= m; i++) left.push_back(ans[i]);
    for (int i = m+1; i <= r; i++) right.push_back(ans[i]);

    int i = 0, j = 0;
    while (i < left.size() and j < right.size()) {
        bool smol = Query(left[i], right[j]);
        
        if (!smol) {
            temp.push_back(left[i++]);
        } else {
            temp.push_back(right[j++]);
        }
    }

    while (i < left.size()) {
        temp.push_back(left[i++]);
    }

    while (j < right.size()) {
        temp.push_back(right[j++]);
    }

    assert(temp.size() == (r - l + 1));

    for (int i = 0; i < temp.size(); i++) {
        ans[i + l] = temp[i];
    }
}

void flip(int l, int r) {
    reverse(ans.begin() + l, ans.begin() + r + 1);    
}

void fix(int N) {
    vector<int> cnt(N);
    for (int i = 0; i < N; i++) {
        for (int j = i+1; j < N; j++) {
            bool smol = Query(ans[i], ans[j]);
            (smol ? ++cnt[i] : ++cnt[j]);
        }
    }

    int zero = -1;
    for (int i = 0; i < N; i++) {
        if (cnt[i] == 0) {
            zero = i;
        }
    }

    if (zero == -1) {
        int u = -1, v = -1;
        for (int i = 0; i < N; i++) {
            if (cnt[i] == 1) {
                u = i;
                break;
            }
        }

        for (int i = u+1; i < N; i++) {
            if (cnt[i] == 1) {
                v = i;
                break;
            }
        }

        bool smol = Query(ans[u], ans[v]);
        zero = (smol ? u : v);
    }

    flip(0, zero);

    int last = zero;
    for (int i = last + 1; i < N; i++) {
        bool smol = Query(ans[last], ans[i]);
        if (smol) {
            flip(last + 1, i);
            last = i;
        }
    }
}

vector<int> Solve(int N) {
    ans.resize(N);
    iota(all(ans), 0);

    work(0, N-1);

    // for (auto &x : ans) {
    //     cerr << x << " ";
    // }   cerr << endl;

    fix(N);

    // for (auto &x : ans) {
    //     cerr << x << " ";
    // }   cerr << endl;

    vector<int> str(N);

    for (int i = 0; i < N; i++) {
        str[ans[i]] = i;
    }

    // for (auto &x : str) {
    //     cerr << x << " ";
    // }   cerr << endl;

    return str;
}

// 5
// 3 1 4 2 0
// 1 0 2 4 3

// 8
// 4 7 3 2 1 5 6 0

// 4 7 0 2 3 1 6 5
// 1 0 4 3 2 7 6 5

// 1 0 5 6 3 2 7 4
// 7 4 5 6 2 3 0 1

// 4 7 2 3 6 5 0 1
// 1 0 3 2 6 5 4 7

// 7 4 3 2 0 5 6 1

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