제출 #1141522

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141522		dombly	Art Collections (BOI22_art)	C++20	5 / 100	5 ms	408 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);
    vector<int>sol = order;
    for(int i = 1; i <= 1000; i++) {
        random_shuffle(order.begin(),order.end());
        if(publish(order) == 0) {
            sol = order;
            break;
        }
    }
    answer(sol);
}

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