Submission #951697

#	Time	Username	Problem	Language	Result	Execution time	Memory
951697		arbuzick	Monster Game (JOI21_monster)	C++17	10 / 100	122 ms	1760 KiB

monster

#include "monster.h"

#include <bits/stdc++.h>

using namespace std;

mt19937 rnd(57);

int get_mx(vector<int> nw) {
    int ans = nw[0];
    for (int i = 1; i < (int)nw.size(); ++i) {
        if (Query(nw[i], ans)) {
            ans = nw[i];
        }
    }
    return ans;
}

int get_mn(vector<int> nw) {
    int ans = nw[0];
    for (int i = 1; i < (int)nw.size(); ++i) {
        if (Query(ans, nw[i])) {
            ans = nw[i];
        }
    }
    return ans;
}

vector<int> my_sort(vector<int> nw) {
    if (nw.size() <= 1) {
        return nw;
    }
    if (nw.size() <= 20) {
        map<pair<int, int>, int> vl;
        map<int, int> cnt;
        for (int i = 0; i < (int)nw.size(); ++i) {
            for (int j = i + 1; j < (int)nw.size(); ++j) {
                if (Query(nw[i], nw[j])) {
                    vl[{nw[i], nw[j]}] = 1;
                    cnt[nw[i]]++;
                } else {
                    vl[{nw[j], nw[i]}] = 1;
                    cnt[nw[j]]++;
                }
            }
        }
        int start;
        for (int i = 0; i < (int)nw.size(); ++i) {
            if (cnt[nw[i]] == 1) {
                bool check = true;
                for (int j = 0; j < (int)nw.size(); ++j) {
                    if (vl[{nw[i], nw[j]}] && cnt[nw[j]] != 1) {
                        check = false;
                        break;
                    }
                }
                if (check) {
                    start = nw[i];
                    break;
                }
            }
        }
        vector<int> ans = {start};
        set<int> used = {start};
        while (ans.size() < nw.size()) {
            for (int i = 0; i < (int)nw.size(); ++i) {
                if (!used.count(nw[i]) && vl[{ans.back(), nw[i]}]) {
                    ans.push_back(nw[i]);
                    used.insert(nw[i]);
                    break;
                }
            }
        }
        return ans;
    }
    vector<int> ord_check = nw;
    shuffle(ord_check.begin(), ord_check.end(), rnd);
    for (auto val_md : ord_check) {
        vector<int> l, r;
        for (int i = 0; i < (int)nw.size(); ++i) {
            if (nw[i] == val_md) {
                continue;
            }
            if (Query(val_md, nw[i])) {
                l.push_back(nw[i]);
            } else {
                r.push_back(nw[i]);
            }
        }
        if (l.size() <= 3 || r.size() <= 3) {
            continue;
        }
        int l_mx = get_mx(l), r_mn = get_mn(r);
        vector<int> ll, rr;
        for (auto vl : l) {
            if (vl != l_mx) {
                ll.push_back(vl);
            }
        }
        ll.push_back(r_mn);
        for (auto vl : r) {
            if (vl != r_mn) {
                rr.push_back(vl);
            }
        }
        rr.push_back(l_mx);
        ll = my_sort(ll);
        rr = my_sort(rr);
        vector<int> ans = ll;
        // ans.push_back(r_mn);
        ans.push_back(val_md);
        // ans.push_back(l_mx);
        for (auto vl : rr) {
            ans.push_back(vl);
        }
        return ans;
    }
    exit(1);
}

vector<int> Solve(int n) {
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    shuffle(ord.begin(), ord.end(), rnd);
    for (int i = 0; i + 1 < n; i += 2) {
        Query(ord[i], ord[i + 1]);
    }
    ord = my_sort(ord);
    vector<int> ans(n);
    for (int i = 0; i < n; ++i) {
        ans[ord[i]] = i;
    }
    return ans;
}

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