oj.uz

Submission #951683

# Submission time Handle Problem Language Result Execution time Memory
951683 2024-03-22T10:25:43 Z arbuzick Monster Game (JOI21_monster) C++17
0 / 100
 120 ms 1864 KB 
#include <bits/stdc++.h>

#include "monster.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() <= 200) {
        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]);
                    break;
                }
            }
        }
        return ans;
    }
    int pos_md = rnd() % nw.size();
    int val_md = nw[pos_md];
    vector<int> l, r;
    for (int i = 0; i < (int)nw.size(); ++i) {
        if (i == pos_md) {
            continue;
        }
        if (Query(val_md, nw[i])) {
            l.push_back(nw[i]);
        } else {
            r.push_back(nw[i]);
        }
    }
    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);
        }
    }
    for (auto vl : r) {
        if (vl != r_mn) {
            rr.push_back(vl);
        }
    }
    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;
}

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 0 ms 344 KB Wrong Answer [3]
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 0 ms 344 KB Wrong Answer [3]
5 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 120 ms 1864 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -