이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |