Submission #895297

#	Time	Username	Problem	Language	Result	Execution time	Memory
895297		GrandTiger1729	Monster Game (JOI21_monster)	C++17	100 / 100	57 ms	848 KiB

monster

#include "monster.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> Solve(int n)
{
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    function<void(int, int)> solve = [&](int l, int r)
    {
        if (l == r - 1)
        {
            return;
        }
        int mid = (l + r) / 2;
        solve(l, mid);
        solve(mid, r);
        int i = l, j = mid;
        vector<int> res;
        while (i < mid && j < r)
        {
            if (!Query(ord[i], ord[j]))
            {
                res.push_back(ord[i]);
                i++;
            }
            else
            {
                res.push_back(ord[j]);
                j++;
            }
        }
        while (i < mid)
        {
            res.push_back(ord[i]);
            i++;
        }
        while (j < r)
        {
            res.push_back(ord[j]);
            j++;
        }
        for (int k = l; k < r; k++)
        {
            ord[k] = res[k - l];
        }
    };
    solve(0, n);
    auto solve4 = [&]()
    {
        if (Query(ord[0], ord[3]))
        {
            swap(ord[0], ord[2]);
        }
        else if (Query(ord[1], ord[3]))
        {
            swap(ord[1], ord[2]);
        }
        else
        {
            swap(ord[0], ord[1]);
        }
    };
    auto solve6 = [&]()
    {
        for (int i = 0; i < 3; i++)
        {
            for (int j = 3; j < 6; j++)
            {
                if (Query(ord[i], ord[j]))
                {
                    swap(ord[2], ord[i]);
                    swap(ord[3], ord[j]);
                    goto found;
                }
            }
        }
        found:
        if (Query(ord[0], ord[2]))
        {
            swap(ord[0], ord[1]);
        }
        if (Query(ord[3], ord[5]))
        {
            swap(ord[4], ord[5]);
        }
    };
    auto get = [&]() -> int
    {
        if (!Query(ord[0], ord[2]))
        {
            int j = 3;
            while (j < n && !Query(ord[0], ord[j]))
            {
                j++;
            }
            if (Query(ord[1], ord[j]))
            {
                reverse(ord.begin() + 1, ord.begin() + j + 1);
            }
            else
            {
                swap(ord[0], ord[1]);
                reverse(ord.begin() + 2, ord.begin() + j + 1);
            }
            return j + 1;
        }
        if (Query(ord[0], ord[3]))
        {
            if (Query(ord[1], ord[3]))
            {
                int j = 4;
                while (j < n && Query(ord[1], ord[j]))
                {
                    j++;
                }
                reverse(ord.begin(), ord.begin() + j);
                return j;
            }
        }
        if (n == 4)
        {
            solve4();
            return 4;
        }
        if (n == 5)
        {
            swap(ord[3], ord[4]);
            solve4();
            return 5;
        }
        if (n == 6)
        {
            solve6();
            return 6;
        }
        if (!Query(ord[3], ord[5]))
        {
            int j = 6;
            while (j < n && !Query(ord[3], ord[j]))
            {
                j++;
            }
            if (Query(ord[4], ord[j]))
            {
                reverse(ord.begin() + 4, ord.begin() + j + 1);
            }
            else
            {
                swap(ord[3], ord[4]);
                reverse(ord.begin() + 5, ord.begin() + j + 1);
            }
            solve4();
            return j + 1;
        }
        if (Query(ord[3], ord[6]))
        {
            if (Query(ord[4], ord[6]))
            {
                int j = 7;
                while (j < n && Query(ord[4], ord[j]))
                {
                    j++;
                }
                reverse(ord.begin() + 3, ord.begin() + j);
                solve4();
                return j;
            }
        }
        solve6();
        return 6;
    };
    int i = get();
    while (i < n)
    {
        int j = i;
        while (j < n && !Query(ord[i - 1], ord[j]))
        {
            j++;
        }
        reverse(ord.begin() + i, ord.begin() + j + 1);
        i = j + 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