Submission #1188730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188730		Valters07	Art Collections (BOI22_art)	C++20	100 / 100	789 ms	472 KiB

art

#include <bits/stdc++.h>
#include "art.h"
using namespace std;
void solve(int n)
{
    vector<int> vals(n);
    iota(vals.begin(), vals.end(), 1);
    int inv = publish(vals);
    for(int i = 1;i < n;i++)
    {
        vector<int> tmp = vals;
        for(int j = i - 1;j >= 0;j--)
            swap(tmp[j], tmp[j + 1]);
        int inv_ = publish(tmp);         // a_i a_1 a_2 ... a_(i-1) a_(i+1) ... a_n
        int b = (inv_ - inv + i) / 2;    // n.o. elements less than a[i]
        int a = i - b;                   // n.o. elements greater than a[i]
        for(int j = 1;j <= b;j++)
            swap(tmp[j - 1], tmp[j]);
        swap(vals, tmp);                 // faster than vals = tmp
        inv -= a;
    }
    answer(vals);
}

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