# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1212872 | BigBadBully | Art Collections (BOI22_art) | C++20 | 0 ms | 0 KiB |
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <set>
#include <vector>
#include "art.h"
using namespace std;
void solve(signed N)
{
int n = N;
auto comp = [&](int x,int y)->bool
{
//x < y
vector<int> tr;
tr.push_back(x+1);
tr.push_back(y+1);
for (int i = 0; i < n; i++)
if (i != x && i != y)
tr.push_back(i+1);
int a = publish(tr);
swap(tr[0],tr[1]);
int b = publish(tr);
return a < b;
};
function<vector<int>(vector<int>)> srt = [&](vector<int> v)->vector<int>
{
vector<int> a,b;
if (v.size()<=1)
return v;
int piv = rand()%(v.size());
for (int i = 0; i < v.size(); i++)
{
if (i == piv)
continue;
if (comp(v[piv],v[i]))
b.push_back(v[i]);
else
a.push_back(v[i]);
}
vector<int> res;
res = srt(a);
res.push_back(v[piv]);
auto vec = srt(b);
for (int x:vec)
res.push_back(x);
return res;
};
vector<int> bs(n,0);
for (int i = 0; i < n; i++)
bs[i] = i;
auto ans = srt(bs);
for (int&x:ans)x++;
answer(ans);
};