Submission #1035258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035258		CommandMaster	Monster Game (JOI21_monster)	C++17	98 / 100	77 ms	960 KiB

monster

#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>

std::vector<int> Solve(int N) {
    std::vector<int> arr;
    // vector<vector<int>> triangles;
    vector<vector<int>> data(N);

    for (int i = 0; i < N; i++) {
        // for (int v : arr) cout << S[v] << ' ';
        // cout << '\n';

        // cout << "----------\n";

        // for (vector<int> v : triangles) {
        //     for (int c : v)
        //         cout << S[c] << ' ';
        //     cout << '\n';
        // }

        // cout << endl;

        int ins_ind = 0;

        // if (!arr.empty() && !Query(arr[0], i))
        ins_ind = lower_bound(arr.begin(), arr.end(), i, [&](ll a, ll b){return Query(b, a);}) - arr.begin();
        if (2 <= ins_ind && data[arr[ins_ind-1]].empty() && data[arr[ins_ind-2]].size() < 5 && !Query(i, arr[ins_ind - 2])) {
            vector<int>& v = data[arr[ins_ind-2]];
            if (v.empty()) {
                v = {i, arr[ins_ind - 1], arr[ins_ind - 2]};
            } else {
                if (Query(i, v[1])) {
                    v = {v[0], v[1], v[2], i, arr[ins_ind - 1]};
                } else {
                    v = {i, arr[ins_ind - 1], v[2], v[0], v[1]};
                }
            }
            arr.erase(arr.begin() + ins_ind - 1);
        } else if (ins_ind + 1 < arr.size() && data[arr[ins_ind]].empty() && data[arr[ins_ind+1]].size() < 5 && Query(i, arr[ins_ind + 1])) {
            vector<int>& v = data[arr[ins_ind+1]];
            if (v.empty()) {
                v = {arr[ins_ind], i, arr[ins_ind + 1]};
            } else {
                if (Query(i, v[1])) {
                    v = {v[0], v[1], v[2], arr[ins_ind], i};
                } else {
                    v = {arr[ins_ind], i, v[2], v[0], v[1]};
                }
            }
            arr.erase(arr.begin() + ins_ind);
        } else {
            arr.insert(arr.begin() + ins_ind, i);
        }
    }

    // for (int c : arr) cout << S[c] << ' ';
    // cout << "\n-------------\n";
    // for (int c : arr) {
    //     for (int v : data[c]) cout << S[v] << ' ';
    //     cout << '\n';
    // }
    // cout << "-------------\n";

    vector<vector<int>> rarr;

    for (int v : arr) {
        if (data[v].empty()) {
            if (!rarr.empty() && (rarr.back().size() == 3) && !Query(v, rarr.back()[0])) {
                if (Query(v, rarr.back()[1]))
                    rarr.back() = {rarr.back()[1], rarr.back()[2], rarr.back()[0], v};
                else
                    rarr.back() = {v, rarr.back()[2], rarr.back()[0], rarr.back()[1]};
            } else
                rarr.push_back({v});
        } else {
            if (!rarr.empty() && (rarr.back().size() == 1 || rarr.back().size() == 3) && data[v].size() == 3 && !Query(data[v][0], rarr.back()[0]) && !Query(data[v][1], rarr.back()[0])) {
                if (rarr.back().size() == 1) {
                    rarr.back() = {data[v][0], data[v][1], data[v][2], rarr.back()[0]};
                } else {
                    rarr.back() = {data[v][0], data[v][1], data[v][2], rarr.back()[2], rarr.back()[0], rarr.back()[1]};
                }
            }
            else
                rarr.push_back(data[v]);
        }
    }

    for (int i = 0; i + 1 < rarr.size(); i++) {
        if (rarr[i].size() == 1 && rarr[i+1].size() == 1) {
            rarr[i] = {rarr[i+1][0], rarr[i][0]};
            rarr[i+1].clear();
        }
    }


    // for (vector<int> d : rarr) {
    //     for (int c : d) cout << S[c] << ' ';
    //     cout << '\n';
    // }

    arr.clear();
    bool unsure = true;

    for (vector<int> d : rarr) {
        if (d.empty()) continue;
        if (d.size() != 3) {
            if (!arr.empty() && unsure) {
                assert(arr.size() == 3);
                for (int a = 0; a < 3; a++) {
                    arr = {arr[2], arr[0], arr[1]};
                    if (Query(arr[2], d[0])) {
                        arr.insert(arr.end(), d.begin(), d.end());
                        unsure = false;
                        goto OUT;
                    }
                }
            }
            arr.insert(arr.end(), d.begin(), d.end());
            unsure = false;
        } else {
            if (arr.empty()) arr = d;
            else {
                if (unsure) {
                    assert(arr.size() == 3);
                    for (int a = 0; a < 3; a++) {
                        arr = {arr[2], arr[0], arr[1]};
                        for (int b = 0; b < 3; b++) {
                            d = {d[2], d[0], d[1]};
                            if (Query(arr[2], d[0])) {
                                arr.insert(arr.end(), d.begin(), d.end());
                                unsure = false;
                                goto OUT;
                            }
                        }
                    }
                } else {
                    for (int b = 0; b < 2; b++) {
                        d = {d[2], d[0], d[1]};
                        if (Query(arr.back(), d[0])) {
                            arr.insert(arr.end(), d.begin(), d.end());
                            goto OUT;
                        }
                    }
                    d = {d[2], d[0], d[1]};
                    arr.insert(arr.end(), d.begin(), d.end());
                }
            }
        }
        OUT:;
    }

    // for (int v : arr) cout << S[v] << ' ';
    // cout << '\n';

    vector<int> T(N);

    for (int i = 0; i < N; i++) T[arr[i]] = i;


    // cout << "----------\n";

    // for (vector<int> v : triangles) {
    //     for (int c : v)
    //         cout << S[c] << ' ';
    //     cout << '\n';
    // }

    return T;
}

Compilation message (stderr)

monster.cpp: In function 'std::vector<int> Solve(int)':
monster.cpp:42:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         } else if (ins_ind + 1 < arr.size() && data[arr[ins_ind]].empty() && data[arr[ins_ind+1]].size() < 5 && Query(i, arr[ins_ind + 1])) {
      |                    ~~~~~~~~~~~~^~~~~~~~~~~~
monster.cpp:91:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for (int i = 0; i + 1 < rarr.size(); i++) {
      |                     ~~~~~~^~~~~~~~~~~~~

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