Submission #1236550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236550		jasonic	Monster Game (JOI21_monster)	C++20	97 / 100	26 ms	424 KiB

monster

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

#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

vector<int> ans;

void conquer(int l_l, int l_r, int r_l, int r_r) {
    queue<int> a, b;
    for(int i = l_l; i <= l_r; i++) a.push(ans[i]);
    for(int i = r_l; i <= r_r; i++) b.push(ans[i]);

    queue<int> c;
    while(!a.empty() && !b.empty()) {
        if(Query(b.front(), a.front())) {
            c.push(a.front());
            a.pop();
        } else {
            c.push(b.front());
            b.pop();
        }
    }

    while(!b.empty()) {
        c.push(b.front());
        b.pop();
    }

    while(!a.empty()) {
        c.push(a.front());
        a.pop();
    }

    for(int i = l_l; i <= r_r; i++) {
        ans[i] = c.front();
        c.pop();
    }

    // for(auto i : ans) cout << i << ' '; cout << '\n';
}

void divide(int l, int r) {
    if(l != r) {
        int m = (l+r)/2;
        divide(l, m);
        divide(m+1, r);
        conquer(l, m, m+1, r);
    }
}

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

    divide(0, n-1);

    vector<pair<int, int>> revranges;

    bool first = true;

    for(int i = 3; i < n && first; i++) first &= Query(ans[i], ans[1]); 

    int p1 = 0, p2 = 2;
    if(!first) {
        revranges.push_back(make_pair(0, 0));
        p1 = 1, p2 = 3;
    }

    // for(auto i : ans) cerr << i << ' '; cerr << '\n';

    while(p1 < n) {
        if(p2 >= n) {
            revranges.push_back(make_pair(p1, min(n-1, p2)));
            break;
        }

        while(Query(ans[p1], ans[p2]) && p2 < n) {
            p2++;
            if(p2 == n) break;
        }

        p2--;

        revranges.push_back(make_pair(p1, p2));
        // cerr << p1 << ' ' << p2 << '\n';

        p1 = p2 + 1;
        p2 = p1 + 2;
    }

    // if(Query(revranges[0].first, revranges[0].second)) {
    //     revranges[0].first++;
    //     revranges.insert(revranges.begin(), make_pair(0, 0));
    // }

    // for(auto i : revranges) cerr << i.first << ' ' << i.second << '\n';

    vector<int> actualAns(n, -1);

    auto full = [&](pair<int, int> &x){
        // printf("full\n\n");
        for(int j = x.first; j <= x.second; j++) actualAns[x.second - j + x.first] = ans[j];
    };

    auto some = [&](pair<int, int> &x){
        // printf("some\n\n");
        for(int j = x.first; j < x.second; j++) actualAns[x.second - j + x.first - 1] = ans[j];
        actualAns[x.second] = ans[x.second];
    };

    for(auto &i : revranges) {

        if(i.first == i.second) {
            actualAns[i.first] = ans[i.first];
            continue;
        }

        // printf("%d to %d:\n", i.first, i.second);
        if(i.second - i.first > 1) {
            if (i.second - i.first != 2) { // range is length 3
                // printf("%d vs %d\n", i.first + 1, i.second);
                if(Query(ans[i.second], ans[i.first + 1])) some(i);
                else full(i);
            }
        } else full(i);
    }

    for(int i = 0; i < revranges.size(); i++) { 
        pair<int, int> x = revranges[i];

        if(x.second - x.first == 2) {
            // putang ina MO

            // length 3 penis dick

            // printf("%d %d: \n", x.first, x.second);

            if(i) {
                if(Query(actualAns[revranges[i-1].second], ans[x.second])) full(x);
                else some(x);
            } else {
                if(revranges[i+1].second - revranges[i+1].first != 2) { // next one is sorted we can use that
                    if(Query(ans[x.first], actualAns[revranges[i+1].first])) full(x);
                    else some(x);
                } else { // waste three queries because dog problem
                    int alice = Query(ans[x.first], ans[revranges[i+1].first+1]);
                    int bob = Query(ans[x.first + 1], ans[revranges[i+1].first+1]);
                    int cindy = Query(ans[x.first + 2], ans[revranges[i+1].first+1]);

                    if(alice + bob + cindy == 1) { // this value is D, so we can full the next subarray and
                        // printf("stupid\n");
                        some(revranges[i+1]);
                        if(alice) full(x);
                        else some(x);
                    } else {
                        // printf("idiot\n");
                        alice = Query(ans[x.first], ans[revranges[i+1].first+2]);
                        bob = Query(ans[x.first + 1], ans[revranges[i+1].first+2]);
                        cindy = Query(ans[x.first + 2], ans[revranges[i+1].first+2]);
                        full(revranges[i+1]);
                        if(alice) full(x);
                        else some(x);
                    }

                    i++;
                }
            }
        }
    }

    vector<int> ans2(n);

    for(int i = 0; i < n; i++) ans2[actualAns[i]] = i;

    // for(auto i : actualAns) cout << i << ' '; cout << '\n';
    // for(auto i : ans2) cout << i << ' '; cout << '\n';

    return ans2;
}

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