Submission #895681

#	Time	Username	Problem	Language	Result	Execution time	Memory
895681		Alcabel	Monster Game (JOI21_monster)	C++17	94 / 100	51 ms	852 KiB

monster

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

void sort(int l, int r, vector<int>& order) {
    if (l + 1 >= r) {
        return;
    }
    int m = l + (r - l) / 2;
    sort(l, m, order);
    sort(m, r, order);
    vector<int> tmp(r - l);
    int ptrL = l, ptrR = m, ptr = 0;
    while (ptrL < m && ptrR < r) {
        if (Query(order[ptrR], order[ptrL])) {
            tmp[ptr++] = order[ptrL++];
        } else {
            tmp[ptr++] = order[ptrR++];
        }
    }
    while (ptrL < m) {
        tmp[ptr++] = order[ptrL++];
    }
    while (ptrR < r) {
        tmp[ptr++] = order[ptrR++];
    }
    for (int i = 0; i < r - l; ++i) {
        order[l + i] = tmp[i];
    }
}

vector<int> Solve(int n) {
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(0, n, order);
    int cntWin = 0, firstWin = n, firstLoss = n;
    for (int i = 1; i < n; ++i) {
        if (Query(order[0], order[i])) {
            ++cntWin;
            firstWin = min(i, firstWin);
        } else {
            firstLoss = min(i, firstLoss);
        }
    }
    int border = -1;
    if (cntWin > 1 && cntWin < n - 2) {
        // order[cntWin] = 0;
        border = cntWin + 1;
    } else if (cntWin == 1) {
        // order[0] = 1 or 0
        if (firstWin == 1) {
            border = 1;
        } else {
            if (firstWin >= 3) {
                if (Query(order[firstWin], order[1])) {
                    border = 2;
                } else {
                    border = 1;
                }
            } else {
                bool moreWon = false;
                vector<int> rask(n - 3);
                iota(rask.begin(), rask.end(), 3);
                mt19937 rnd(161);
                shuffle(rask.begin(), rask.end(), rnd);
                for (const int& i : rask) {
                    if (Query(order[2], order[i])) {
                        moreWon = true;
                        break;
                    }
                }
                if (moreWon) {
                    border = 2;
                } else {
                    border = 1;
                }
            }
        }
    } else {
        // order[0] = n - 1 or n - 2
        if (Query(order[n - 3], order[n - 1])) {
            border = n;
        } else {
            border = n - 1;
        }
    }
    reverse(order.begin(), order.begin() + border);
    while (border < n - 1) {
        int newBorder = border;
        while (!Query(order[border - 1], order[newBorder])) {
            ++newBorder;
        }
        reverse(order.begin() + border, order.begin() + newBorder + 1);
        border = newBorder + 1;
    }
    vector<int> ans(n);
    for (int i = 0; i < n; ++i) {
        ans[order[i]] = i;
    }
    return ans;
}
/*
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    return 0;
}
*/

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