Submission #812650

#	Time	Username	Problem	Language	Result	Execution time	Memory
812650		Hanksburger	Fun Tour (APIO20_fun)	C++17	21 / 100	439 ms	93924 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
int ok[100005], depth[100005], n;
set<pair<int, int> > s[100005];
vector<int> ans;
void dfs(int u)
{
    s[u].insert({-depth[u], u});
    if (u*2+1<n)
    {
        depth[u*2+1]=depth[u]+1;
        dfs(u*2+1);
        s[u].insert(s[u*2+1].begin(), s[u*2+1].end());
    }
    if (u*2+2<n)
    {
        depth[u*2+2]=depth[u]+1;
        dfs(u*2+2);
        s[u].insert(s[u*2+2].begin(), s[u*2+2].end());
    }
}
vector<int> createFunTour(int nn, int qq)
{
    n=nn;
    dfs(0);
    for (int i=0; i<n; i++)
        ok[i]=1;
    int cur=n-1;
    ok[cur]=0;
    ans.push_back(cur);
    {
        int u=cur;
        while (u)
        {
            s[u].erase({-depth[cur], cur});
            u=(u-1)/2;
        }
        s[u].erase({-depth[cur], cur});
    }
    for (int i=1; i<n; i++)
    {
        int u=cur, cnt=1, mx=0, ind;
        while (u)
        {
            cnt++;
            if (u&1 && ok[u+1])
            {
                if (mx<cnt-depth[u+1]-(*s[u+1].begin()).first)
                {
                    mx=cnt-depth[u+1]-(*s[u+1].begin()).first;
                    ind=(*s[u+1].begin()).second;
                }
            }
            else if (u%2==0 && ok[u-1])
            {
                if (mx<cnt-depth[u-1]-(*s[u-1].begin()).first)
                {
                    mx=cnt-depth[u-1]-(*s[u-1].begin()).first;
                    ind=(*s[u-1].begin()).second;
                }
            }
            u=(u-1)/2;
        }
        if (mx)
            cur=ind;
        else
            cur=(cur-1)/2;
        ok[cur]=0;
        ans.push_back(cur);
        {
            int u=cur;
            while (u)
            {
                s[u].erase({-depth[cur], cur});
                u=(u-1)/2;
            }
            s[u].erase({-depth[cur], cur});
        }
    }
    return ans;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 16
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34