Submission #1212874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212874		BigBadBully	Art Collections (BOI22_art)	C++20	20 / 100	56 ms	428 KiB

art

#include <bits/stdc++.h>


#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);
    
};

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