oj.uz

Submission #951689

# Submission time Handle Problem Language Result Execution time Memory
951689 2024-03-22T10:41:41 Z arbuzick Monster Game (JOI21_monster) C++17
0 / 100
 2000 ms 856 KB 
#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() == 1 || r.size() == 1) {
            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);
            }
        }
        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;
}

Compilation message

monster.cpp: In function 'std::vector<int> my_sort(std::vector<int>)':
monster.cpp:76:29: warning: control reaches end of non-void function [-Wreturn-type]
   76 |     vector<int> ord_check = nw;
      |                             ^~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 600 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Execution timed out 3050 ms 856 KB Time limit exceeded
17 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 1 ms 340 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 600 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Execution timed out 3050 ms 856 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3029 ms 856 KB Time limit exceeded
2 Halted 0 ms 0 KB -