제출 #951691

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
951691		arbuzick	Monster Game (JOI21_monster)	C++17	25 / 100	118 ms	1660 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() <= 4 || r.size() <= 4) {
            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;
}

컴파일 시 표준 에러 (stderr) 메시지

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: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 0 / 75