제출 #951842

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
951842		arbuzick	Monster Game (JOI21_monster)	C++17	100 / 100	71 ms	2708 KiB

monster

#include "monster.h"

#include <bits/stdc++.h>

using namespace std;

map<pair<int, int>, bool> mp;

bool query(int i, int j) {
    if (mp.count({i, j})) {
        return mp[{i, j}];
    }
    mp[{i, j}] = Query(i, j);
    mp[{j, i}] = !mp[{i, j}];
    return mp[{i, j}];
}

vector<int> my_sort(vector<int> nw) {
    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> Solve(int n) {
    vector<int> ord = {0};
    for (int i = 1; i < n; ++i) {
        int l = -1, r = ord.size();
        while (l < r - 1) {
            int m = (l + r) / 2;
            if (query(i, ord[m])) {
                l = m;
            } else {
                r = m;
            }
        }
        vector<int> ord_nw;
        for (int j = 0; j <= l; ++j) {
            ord_nw.push_back(ord[j]);
        }
        ord_nw.push_back(i);
        for (int j = r; j < (int)ord.size(); ++j) {
            ord_nw.push_back(ord[j]);
        }
        ord = ord_nw;
    }
    // for (int i = 0; i < n; ++i) {
    //     cout << ord[i] << ' ';
    // }
    // cout << endl;
    int pos = 0;
    vector<int> poses;
    while (pos < n - 2) {
        int r = pos + 2;
        if (query(ord[pos], ord[r])) {
            while (r + 1 < n && query(ord[pos], ord[r + 1])) {
                r++;
            }
            if (r == pos + 2) {
                poses.push_back(pos);
            } else {
                if (query(ord[pos + 1], ord[r])) {
                    reverse(ord.begin() + pos, ord.begin() + r + 1);
                } else {
                    reverse(ord.begin() + pos, ord.begin() + r);
                }
            }
        } else {
            while (r + 1 < n && query(ord[r + 1], ord[pos])) {
                r++;
            }
            if (r > pos + 2) {
                if (query(ord[r], ord[pos + 1])) {
                    reverse(ord.begin() + pos, ord.begin() + pos + 2);
                    reverse(ord.begin() + pos + 2, ord.begin() + r + 2);
                    r++;
                } else {
                    reverse(ord.begin() + pos + 1, ord.begin() + r + 2);
                    r++;
                }
            } else {
                vector<int> vals = {ord[pos], ord[pos + 1], ord[pos + 2], ord[pos + 3]};
                vals = my_sort(vals);
                ord[pos] = vals[0];
                ord[pos + 1] = vals[1];
                ord[pos + 2] = vals[2];
                ord[pos + 3] = vals[3];
                r++;
            }
        }
        pos = r + 1;
    }
    if (pos == n - 2) {
        swap(ord[n - 2], ord[n - 1]);
    }
    for (int i = 0; i < (int)poses.size(); ++i) {
        if (poses[i] == -1) {
            continue;
        }
        if (poses[i] != 0) {
            vector<int> vals = {ord[poses[i] - 1], ord[poses[i]], ord[poses[i] + 1], ord[poses[i] + 2]};
            vals = my_sort(vals);
            ord[poses[i]] = vals[1];
            ord[poses[i] + 1] = vals[2];
            ord[poses[i] + 2] = vals[3];
        } else if (i + 1 == (int)poses.size() || poses[i] + 3 != poses[i + 1]) {
            vector<int> vals = {ord[poses[i]], ord[poses[i] + 1], ord[poses[i] + 2], ord[poses[i] + 3]};
            vals = my_sort(vals);
            ord[poses[i]] = vals[0];
            ord[poses[i] + 1] = vals[1];
            ord[poses[i] + 2] = vals[2];
        } else {
            vector<int> vals = {ord[poses[i]], ord[poses[i] + 1], ord[poses[i] + 2], ord[poses[i] + 3], ord[poses[i] + 4], ord[poses[i] + 5]};
            vals = my_sort(vals);
            ord[poses[i]] = vals[0];
            ord[poses[i] + 1] = vals[1];
            ord[poses[i] + 2] = vals[2];
            ord[poses[i] + 3] = vals[3];
            ord[poses[i] + 4] = vals[4];
            ord[poses[i] + 5] = vals[5];
            poses[i + 1] = -1;
        }
    }
    vector<int> ans(n);
    for (int i = 0; i < n; ++i) {
        ans[ord[i]] = i;
    }
    return ans;
}

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