Submission #436332

#	Time	Username	Problem	Language	Result	Execution time	Memory
436332		LouayFarah	Fun Tour (APIO20_fun)	C++14	26 / 100	26 ms	1356 KiB

fun

#include "bits/stdc++.h"
#include "fun.h"
 
using namespace std;
 
#define pb push_back
 
int fast_pow(int a, int b)
{
    if(b==0)
        return 1;

    int u = fast_pow(a, b/2);
    u = u*u;
    if(b%2==1)
        u*=a;

    return u;
}

vector<int> createFunTour(int n, int q)
{
    if(n<=500)
    {
        vector<vector<int>> dist(n, vector<int>(n, 0));
        for(int i = 0; i<n; i++)
        {
            for(int j = 0; j<n; j++)
            {
                dist[i][j] = hoursRequired(i, j);
            }
        }

        int u = 0;
        int ma = 0;
        for(int i = 0; i<n; i++)
        {
            for(int j = 0; j<n; j++)
            {
                if(dist[i][j]>ma)
                {
                    ma = dist[i][j];
                    u = i;
                }
            }
        }

        vector<bool> visited(n, false);

        vector<int> res;
        while((int)res.size()<n)
        {
            res.pb(u);
            visited[u] = true;
            int maxi = 0;
            int v = 0;
            for(int i = 0; i<n; i++)
            {
                if(visited[i])
                    continue;
                if(dist[u][i]>maxi)
                {
                    v = i;
                    maxi = dist[u][i];
                }
            }
            u = v;
        }

        return res;
    }
    else
    {
        int ptr1, ptr2, pow1, pow2;
        int deg = 0;
        int temp = n+1;

        while(temp>1)
        {
            temp/=2;
            deg++;
        }

        if(n-1>=fast_pow(2, deg) + fast_pow(2, deg-1)-1)
        {
            ptr2 = n-1;
            ptr1 = fast_pow(2, deg) + fast_pow(2, deg-1)-2;
            pow1 = deg, pow2 = deg;
        }
        else
        {
            ptr2 = fast_pow(2, deg) -2;
            pow2 = deg-1;
            ptr1 = n-1;
            pow1 = deg;
        }

        vector<int> res;

        bool flag = true;
        while((int)res.size()<n)
        {
            if(flag)
            {
                res.pb(ptr1);
                ptr1--;
                if(ptr1==fast_pow(2, pow1)-2)
                {
                    pow1--;
                    ptr1 = fast_pow(2, pow1) + fast_pow(2, pow1-1) -2;
                }
            }
            else
            {
                if(ptr2<0)
                {
                    flag = !flag;
                    continue;
                }
                res.pb(ptr2);
                ptr2--;
                if(ptr2==fast_pow(2, pow2) + fast_pow(2, pow2-1)-2)
                {
                    ptr2 = fast_pow(2, pow2) -2 ;
                    pow2--;
                }
            }
            flag = !flag;
        }
        return res;
    }

}

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