Submission #1188737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188737		Valters07	Art Collections (BOI22_art)	C++20	35 / 100	93 ms	420 KiB

art

#include <bits/stdc++.h>
#include "art.h"
#define pb push_back
using namespace std;
int n;
bool cmp(int a, int b)
{
    vector<int> ve;
    ve.pb(a);
    ve.pb(b);
    for(int i = 1;i <= n;i++)
        if(i != a && i != b)
            ve.pb(i);
    int inv = publish(ve);
    swap(ve[0], ve[1]);
    int inv2 = publish(ve);
    return (inv < inv2);
}
void merge_sort(vector<int> &vals, int l, int r)
{
    if(l == r)
        return;
    int mid = (l + r) / 2;
    merge_sort(vals, l, mid);
    merge_sort(vals, mid + 1, r);
    vector<int> tot;
    int it1 = l, it2 = mid + 1;
    while(it1 <= mid || it2 <= r)
    {
        if(it1 <= mid && it2 <= r)
        {
            if(cmp(vals[it1], vals[it2]))
                tot.pb(vals[it1++]);
            else
                tot.pb(vals[it2++]);
        }
        else if(it1 <= mid)
            tot.pb(vals[it1++]);
        else
            tot.pb(vals[it2++]);
    }
    for(int i = l;i <= r;i++)
        vals[i] = tot[i - l];
}
void solve(int N)
{
    n = N;
    vector<int> vals(n);
    iota(vals.begin(), vals.end(), 1);
    merge_sort(vals, 0, vals.size() - 1);
    answer(vals);
}

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