제출 #679797

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
679797		bashkort	Monster Game (JOI21_monster)	C++17	89 / 100	141 ms	1896 KiB

monster

#include <bits/stdc++.h>
#include "monster.h"

using namespace std;

mt19937 rnd(228);

vector<int> Solve(int n) {
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);

    shuffle(ord.begin(), ord.end(), rnd);

    map<pair<int, int>, bool> asked;
    auto ask = [&](int i, int j) {
        if (!asked.count({i, j})) {
            asked[{i, j}] = Query(i, j);
            asked[{j, i}] = !asked[{i, j}];
        }
        return asked[{i, j}];
    };

    stable_sort(ord.begin(), ord.end(), [&](int i, int j) {
        return !ask(i, j);
    });

//    auto merge_sort = [&](auto self, vector<int> a) -> vector<int> {
//        if (a.size() == 1) {
//            return a;
//        }
//        int mid = a.size() / 2;
//        auto L = self(self, vector(a.begin(), a.begin() + mid));
//        auto R = self(self, vector(a.begin() + mid, a.end()));
//        a.clear();
//        int i = 0, j = 0;
//        while (i < L.size() || j < R.size()) {
//            if (i < L.size() && (j == R.size() || !ask(L[i], R[j]))) {
//                a.push_back(L[i++]);
//            } else {
//                a.push_back(R[j++]);
//            }
//        }
//        return a;
//    };
//
//    ord = merge_sort(merge_sort, ord);

    auto is_n = [&](int i) {
        int killer = -1;
        int skipped = 0;
        for (int k = 0; k < n && skipped < 2; ++k) {
            if (k == i) continue;
            if (ask(ord[i], ord[k])) {
            } else {
                ++skipped;
                killer = k;
            }
        }
        if (skipped == 1) {
            int kek = 0;
            skipped = 0;
            for (int k = 0; k < i && skipped < 2; ++k) {
                if (k == i) continue;
                if (k != killer) {
                    bool now = ask(ord[killer], ord[k]);
                    if (!now) {
                        skipped += 1;
                    }
                }
            }
            if (skipped == 1) {
                return true;
            }
        }
        return false;
    };

    bool damn = false;

    for (int i = n - 1; i > 0;) {
        if (i == n - 1) {
            if (is_n(i)) {
                --i;
                continue;
            }
        }
        if (damn || i + 1 < n && ask(ord[i], ord[i + 1])) {
            --i;
            damn = false;
            continue;
        }
        damn = false;
        int j = i - 2;
        while (j >= 0 && ask(ord[j], ord[i])) {
            --j;
        }
        if (i - j > 3 && ask(ord[i - 1], ord[j + 1])) {
            ++j;
            damn = true;
        } else if (i - j == 3) {
            if (i == n - 1) {
                if (is_n(i - 1)) {
                    swap(ord[i], ord[i - 1]);
                } else {
                    swap(ord[i - 2], ord[i]);
                }
            } else {
                if (ask(ord[i - 1], ord[i + 1])) {
                    swap(ord[i], ord[i - 1]);
                } else {
                    swap(ord[i - 2], ord[i]);
                }
            }
            i -= 3;
            continue;
        }
        reverse(ord.begin() + j + 1, ord.begin() + i + 1);
        i = j;
    }

    vector<int> ans(n);
    for (int i = 0; i < n; ++i) {
        ans[ord[i]] = i;
    }


    return ans;
}

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

monster.cpp: In lambda function:
monster.cpp:60:17: warning: unused variable 'kek' [-Wunused-variable]
   60 |             int kek = 0;
      |                 ^~~
monster.cpp: In function 'std::vector<int> Solve(int)':
monster.cpp:87:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   87 |         if (damn || i + 1 < n && ask(ord[i], ord[i + 1])) {
      |                     ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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