Submission #1322513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1322513		simona1230	Art Collections (BOI22_art)	C++20	100 / 100	1104 ms	262904 KiB

art

#include "art.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> nxt[200001];
pair<int,int> cnt[200001];
map<vector<int>, int> mp,in;

int publish_(vector<int> v)
{
    if(!in[v])mp[v]=publish(v);
    in[v]=1;
    return mp[v];
}

void solve(int N)
{
    vector<int> v={1};
    n=N;

    for(int i=2;i<=n;i++)
    {
        vector<int> v1=v,v2={i};
        v1.push_back(i);
        for(int j=0;j<v.size();j++)
            v2.push_back(v[j]);

        for(int j=i+1;j<=n;j++)
        {
            v1.push_back(j);
            v2.push_back(j);
        }

        int p1=publish_(v1);
        int p2=publish_(v2);

        int b=(i-1-p1+p2)/2;
        int a=i-1-b;

        vector<int> nw;
        for(int j=0;j<b;j++)
            nw.push_back(v[j]);
        nw.push_back(i);
        for(int j=0;j<a;j++)
            nw.push_back(v[j+b]);
        v=nw;

        for(int j=i+1;j<=n;j++)
            nw.push_back(j);
        in[nw]=1;
        mp[nw]=mp[v2]-b;
    }

    answer(v);
}

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