oj.uz

Submission #951681

# Submission time Handle Problem Language Result Execution time Memory
951681 2024-03-22T10:13:17 Z arbuzick Monster Game (JOI21_monster) C++17
0 / 100
 11 ms 856 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;
    }
    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 Incorrect 0 ms 344 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -