Submission #291394

#	Time	Username	Problem	Language	Result	Execution time	Memory
291394		muhammad_hokimiyon	Fun Tour (APIO20_fun)	C++14	21 / 100	187 ms	18292 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>

#define fi first
#define se second

using namespace std;

const int NN = 1e5 + 7;



vector<int> createFunTour(int N, int Q)
{
    if( N == 2 ){
        vector < int > res;
        res.push_back(0);
        res.push_back(1);
        return res;
    }
    set < pair < int , int > > s[3];
    int cntr = 0;
    for( int i = 1; i < N; i++ ){
        if( attractionsBehind(0 , i) * 2 > N ){
            cntr = i;
        }
    }
    vector < int > d(N , 0);
    for( int i = 0; i < N; i++ ){
        if( i == cntr )continue;
        d[i] = hoursRequired( i , cntr );
    }
    vector < int > gr;
    for( int i = 0; i < N; i++ ){
        if( d[i] == 1 ){
            gr.push_back(i);
            s[(int)gr.size() - 1].insert({ d[i] , i });
        }
    }
    for( int i = 0; i < N; i++ ){
        bool f = false;
        if( i == cntr )continue;
        for( auto x : gr )f |= (i == x);
        if( f )continue;
        for( int j = 0; j < (int)gr.size() - 1; j++ ){
            if( hoursRequired( gr[j] , i ) + 1 == d[i] ){
                f = true;
                s[j].insert({ d[i] , i });
                break;
            }
        }
        if( !f ){
            s[(int)gr.size() - 1].insert({ d[i] , i });
        }
    }
    auto x = *(--s[0].end());
    auto y = *(--s[1].end());
    if( !s[2].empty() && (--s[2].end())->fi > x.fi ){
        if( x.fi > y.fi ){
            y = x;
        }
        x = *(--s[2].end());
    }
    else if( !s[2].empty() && (--s[2].end())->fi > y.fi ){
        if( y.fi > x.fi ){
            x = y;
        }
        y = *(--s[2].end());
    }
    vector < int > res;
    res.push_back(x.se);
    s[0].erase(x);
    for( int i = 0; i < N - 2; i++ ){
        x = {0 , 0};
        int tp = 0;
        for( int j = 0; j < 3; j++ ){
            if( s[j].find(y) != s[j].end() ){
                tp = j;
            }
        }
        int f = 0;
        for( int j = 0; j < 3; j++ ){
            if( tp == j || s[j].empty() )continue;
            if( j == 0 ){
                if( tp == 1 )f = 2;
                else f = 1;
            }else{
                if( j == 1 ){
                    if( tp == 0 )f = 2;
                    else f = 0;
                }else{
                    if( tp == 0 )f = 1;
                    else f = 0;
                }
            }
            if( (int)s[j].size() + (int)s[tp].size() <= (int)s[f].size() ){
                continue;
            }
            x = max( x , *(--s[j].end()) );
        }
        res.push_back( y.se );
        s[tp].erase(y);
        y = x;
    }
    res.push_back(cntr);
    return res;
}

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