Submission #1141062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141062		dombly	Art Collections (BOI22_art)	C++20	50 / 100	371 ms	440 KiB

art

#include <bits/stdc++.h>
#include "art.h"
#define pb push_back

using namespace std;

int inv;
vector<int>order;

vector<int> Solve(int l,int r) {
    if(l == r) return {l};
    int mid = l + r >> 1;
    vector<int>L = Solve(l,mid);
    vector<int>R = Solve(mid + 1,r);
    int ptr1 = 0,ptr2 = 0,n1 = L.size(),n2 = R.size();
    vector<int>v;
    while(ptr1 < n1 || ptr2 < n2) {
        if(ptr1 == n1) {
            v.pb(R[ptr2++]);
        }else if(ptr2 == n2) {
            v.pb(L[ptr1++]);
        }else {
            assert(L[ptr1] - 1 >= 0 && L[ptr1] - 1 <= r);
            assert(R[ptr2] - 1 >= 0 && R[ptr2] - 1 <= r);
            swap(order[L[ptr1] - 1],order[R[ptr2] - 1]);
            int inv2 = publish(order);
            swap(order[L[ptr1] - 1],order[R[ptr2] - 1]);
            if(inv2 < inv) v.pb(R[ptr2++]);
            else v.pb(L[ptr1++]);
        }
    }
    return v;
}

void solve(int N) {
    for(int i = 1; i <= N; i++) order.pb(i);
    inv = publish(order);
    answer(Solve(1,N));
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30