Submission #766161

#	Time	Username	Problem	Language	Result	Execution time	Memory
766161		pandapythoner	Monster Game (JOI21_monster)	C++17	100 / 100	85 ms	428 KiB

monster

#include <bits/stdc++.h>

#include "monster.h"

using namespace std;

#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

mt19937 rnd(2342334);

int qcnt;

bool query(int a, int b) {
    qcnt += 1;
    return !Query(a, b);
}

vector<int> merge(vector<int> a, vector<int> b) {
    vector<int> c;
    int i = 0;
    int j = 0;
    while (i < (int)a.size() && j < (int)b.size()) {
        if (query(a[i], b[j])) {
            c.push_back(a[i]);
            i += 1;
        } else {
            c.push_back(b[j]);
            j += 1;
        }
    }
    while (i < (int)a.size()) {
        c.push_back(a[i]);
        i += 1;
    }
    while (j < (int)b.size()) {
        c.push_back(b[j]);
        j += 1;
    }
    return c;
}

vector<int> merge_sort(vector<int> a) {
    if (a.size() == 1) {
        return a;
    }
    int sz = (int)a.size();
    vector<int> x, y;
    for (int i = 0; i < sz; i += 1) {
        if (i < sz / 2) {
            x.push_back(a[i]);
        } else {
            y.push_back(a[i]);
        }
    }
    x = merge_sort(x);
    y = merge_sort(y);
    auto z = merge(x, y);
    return z;
}

vector<int> sort_aboba(vector<int> a) {
    vector<int> b = {a[0]};
    for (int i = 1; i < (int)a.size(); i += 1) {
        int l = -1;
        int r = (int)b.size();
        while (l + 1 < r) {
            int m = (l + r) / 2;
            if (query(b[m], a[i])) {
                l = m;
            } else {
                r = m;
            }
        }
        b.insert(b.begin() + r, a[i]);
    }
    return b;
}

vector<int> Solve(int n) {
    qcnt = 0;
    vector<int> t(n);
    for (int i = 0; i < n; i += 1) {
        t[i] = i;
    }
    shuffle(all(t), rnd);
    t = sort_aboba(t);
    if (query(t[0], t[n - 1])) {
        int x = -1;
        for (int i = min(100, n - 2); i >= 0; i -= 1) {
            if (!query(t[0], t[i])) {
                x = i;
                break;
            }
        }
        if (x == -1) {
            assert(0);
        }
        if (x == 1) {
            assert(0);
        }
        int fuck = -1;
        bool previous_was_1 = false;
        if (x == 2) {
            // assert(n <= 500);
            bool is_1_mx = false;
            int megaaboba = -1;
            for (int i = 3; i < n; i += 1) {
                if (!query(t[1], t[i])) {
                    megaaboba = i;
                    is_1_mx = true;
                    break;
                } else if (!query(t[2], t[i])) {
                    megaaboba = i;
                    break;
                }
            }
            if (is_1_mx) {
                swap(t[1], t[2]);
                reverse(t.begin() + 3, t.begin() + megaaboba + 1);
                fuck = megaaboba + 1;
            } else {
                swap(t[0], t[1]);
                reverse(t.begin() + 3, t.begin() + megaaboba + 1);
                fuck = megaaboba + 1;
            }
        } else {
            int m = x + 1;
            vector<int> q(m - 2);
            for (int i = 0; i < m - 2; i += 1) {
                q[i] = query(t[i], t[i + 2]);
            }
            int d = -1;
            for (int i = 0; i + 1 < m - 2; i += 1) {
                if (q[i] && q[i + 1]) {
                    d = i + 1;
                    break;
                }
            }
            if (d == -1) {
                if (q[0]) {
                    d = 0;
                } else if (q[m - 3]) {
                    d = m - 2;
                }
            }
            if (d == -1) {
                assert(0);
            } else {
                reverse(t.begin(), t.begin() + d + 1);
                reverse(t.begin() + d + 1, t.begin() + m);
            }
            fuck = m;
        }
        while (fuck < n) {
            int new_fuck = -1;
            for (int i = fuck + (int)previous_was_1; i < n; i += 1) {
                if (!query(t[fuck - 1], t[i])) {
                    new_fuck = i + 1;
                    break;
                }
            }
            if (new_fuck == -1) {
                assert(0);
            }
            reverse(t.begin() + fuck, t.begin() + new_fuck);
            previous_was_1 = ((new_fuck - fuck) == 1);
            fuck = new_fuck;
        }
    } else {
        vector<int> q(n - 2);
        for (int i = 0; i < n - 2; i += 1) {
            q[i] = query(t[i], t[i + 2]);
        }
        int d = -1;
        for (int i = 0; i + 1 < n - 2; i += 1) {
            if (q[i] && q[i + 1]) {
                d = i + 1;
                break;
            }
        }
        if (d == -1) {
            if (q[0]) {
                d = 0;
            } else if (q[n - 3]) {
                d = n - 2;
            }
        }
        if (d == -1) {
            reverse(all(t));
        } else {
            reverse(t.begin(), t.begin() + d + 1);
            reverse(t.begin() + d + 1, t.end());
        }
    }
    vector<int> p(n);
    for (int i = 0; i < n; i += 1) {
        p[t[i]] = i;
    }
    return p;
}

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