Submission #1229753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229753		SpyrosAliv	Monster Game (JOI21_monster)	C++20	0 / 100	3 ms	424 KiB

monster

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

int n;

void sort_slow(vector<int> &els, bool hasLeft, bool hasRight) {
    int sz = els.size();
    vector<int> a(sz, -1);
    vector<int> loss(sz, 0), win(sz, 0);
    int idxa = -1, idxb = -1;
    int i2 = -1, j2 = -1;
    vector<int> b4(sz+1, -1);
    for (int i = 0; i < sz; i++) {
        for (int j = i + 1; j < sz; j++) {
            int ans = Query(els[i], els[j]);
            if (ans == true) {
                win[i]++;
                loss[j]++;
            }
            else {
                loss[i]++;
                win[j]++;
            }
        }
        a[i] = abs(loss[i] - sz) - 1;
        if (a[i] == 1 + hasLeft) {
            if (idxa == -1) idxa = i;
            else idxb = i;
        }
        if (a[i] == sz-2 - hasRight) {
            if (i2 == -1) i2 = i;
            else j2 = i;
        }
    }
    cout << "ORDER BEFORE: ";
    for (int i = 0; i < sz; i++) cout << a[i] << " ";
    if (idxa != -1 && idxb != -1) {
        int ans = Query(els[idxa], els[idxb]);
        if (ans) {
            a[idxa] = 0 + hasLeft;
        }
        else a[idxb] = 0 + hasLeft;
    }
    if (i2 != -1 && j2 != -1) {
        int ans = Query(els[i2], els[j2]);
        if (ans) {
            a[j2] = sz-1-hasRight;
        }
        else a[i2] = sz-1-hasRight;
    }
    cout << "ORDER: ";
    for (int i = 0; i < sz; i++) cout << a[i] << " ";
    cout << "\n";
    vector<int> fin(sz);
    for (int i = 0; i < sz; i++) {
        fin[a[i]] = els[i];
    }
    els = fin;
}

vector<int> quick_select(vector<int> curr, bool hasLeft = false, bool hasRight = false) {
    if (curr.size() <= 10) {
        sort_slow(curr, hasLeft, hasRight);
        return curr;
    }
    int sz = curr.size();
    vector<int> small, large;
    int el;
    while (small.size() <= 2 || large.size() <= 2) {
        el = curr[rand() % sz];
        small.clear();
        large.clear();
        for (auto x: curr) {
            if (x == el) continue;
            if (Query(el, x)) {
                small.push_back(x);
            }
            else large.push_back(x);
        }
    }
    cout << el << "\n";
    for (auto x: small) cout << x << " ";
    cout << "\n";
    for (auto x: large) cout << x << " ";
    cout << "\n";
    vector<int> fin;
    small = quick_select(small, hasLeft, true);
    large = quick_select(large, true, hasRight);
    for (auto x: small) cout << x << " ";
    cout << "\n";
    for (auto x: large) cout << x << " ";
    cout << "\n";
    swap(small.back(), large[0]);
    small.push_back(el);
    for (auto x: large) small.push_back(x);
    return small;
}

vector<int> Solve(int N) {
    n = N;
    vector<int> curr;
    for (int i = 0; i < n; i++) curr.push_back(i);
    vector<int> fin = quick_select(curr);
    vector<int> ans(n);
    for (int i = 0; i < n; i++) {
        ans[fin[i]] = i;
    }
    for (int i = 0; i < n; i++) cout << fin[i] << " ";
    cout << "\n";
    return ans;
}

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