Submission #291447

#	Time	Username	Problem	Language	Result	Execution time	Memory
291447		muhammad_hokimiyon	Fun Tour (APIO20_fun)	C++14	31 / 100	188 ms	18288 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 , y = N; i < N; i++ ){
        int x = attractionsBehind(0 , i);
        if( x * 2 >= N && x < y ){
            cntr = i;
            y = x;
        }
    }
    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 });
        }
    }
    if( (int)s[0].size() + (int)s[1].size() <= (int)s[2].size() ){
        for( auto x : s[1] ){
            s[0].insert(x);
        }
        s[1].clear();
        s[1] = s[2];
        s[2].clear();
    }
    if( (int)s[0].size() + (int)s[2].size() <= (int)s[1].size() ){
        for( auto x : s[2] ){
            s[0].insert(x);
        }
        s[2].clear();
    }
    if( (int)s[1].size() + (int)s[2].size() <= (int)s[0].size() ){
        for( auto x : s[2] ){
            s[1].insert(x);
        }
        s[2].clear();
    }
    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);
    int cnt = 0;
    for( int i = 0; i < 3; i++ ){
        if( s[i].find(x) != s[i].end() ){
            s[i].erase(x);
            cnt += 1;
        }
    }
    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;
            }
        }
        if( tp == 0 ){
            if( (int)s[0].size() + (int)s[1].size() <= (int)s[2].size() ){
                x = *(--s[2].end());
            }else if( (int)s[0].size() + (int)s[2].size() <= (int)s[1].size() ){
                x = *(--s[1].end());
            }else{
                for( int j = 0; j < 3; j++ ){
                    if( tp == j || s[j].empty() )continue;
                    x = max( x , *(--s[j].end()) );
                }
            }
        }else{
            if( tp == 1 ){
                if( (int)s[1].size() + (int)s[2].size() <= (int)s[0].size() ){
                    x = *(--s[0].end());
                }else if( (int)s[1].size() + (int)s[0].size() <= (int)s[2].size() ){
                    x = *(--s[2].end());
                }else{
                    for( int j = 0; j < 3; j++ ){
                        if( tp == j || s[j].empty() )continue;
                        x = max( x , *(--s[j].end()) );
                    }
                }
            }else{
                if( (int)s[2].size() + (int)s[1].size() <= (int)s[0].size() ){
                    x = *(--s[0].end());
                }else if( (int)s[2].size() + (int)s[0].size() <= (int)s[1].size() ){
                    x = *(--s[1].end());
                }else{
                    for( int j = 0; j < 3; j++ ){
                        if( tp == j || s[j].empty() )continue;
                        x = max( x , *(--s[j].end()) );
                    }
                }
            }
        }
        int f = 0;
        res.push_back( y.se );
        assert( s[tp].find(y) != s[tp].end() );
        s[tp].erase(y);
        y = x;
    }
    res.push_back(cntr);
    return res;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:145:13: warning: unused variable 'f' [-Wunused-variable]
  145 |         int f = 0;
      |             ^

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