제출 #291404

#제출 시각아이디문제언어결과실행 시간메모리
291404muhammad_hokimiyon즐거운 행로 (APIO20_fun)C++14
21 / 100
220 ms18288 KiB
#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 }); } } if( (int)s[0].size() + (int)s[1].size() <= (int)s[2].size() ){ for( auto x1 : s[0] ){ s[1].insert(x1); } s[0].clear(); s[0] = s[2]; s[2].clear(); } if( (int)s[0].size() + (int)s[2].size() <= (int)s[1].size() ){ for( auto x1 : s[2] ){ s[0].insert(x1); } s[2].clear(); } if( (int)s[1].size() + (int)s[2].size() <= (int)s[0].size() ){ for( auto x1 : s[2] ){ s[1].insert(x1); } 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); for( int i = 0; i < 3; i++ ){ if( s[i].find(x) != s[i].end() ){ s[i].erase(x); } } for( int i = 0; i < N - 2; i++ ){ if( (int)s[0].size() + (int)s[1].size() <= (int)s[2].size() ){ for( auto x1 : s[0] ){ s[1].insert(x1); } s[0].clear(); } if( (int)s[0].size() + (int)s[2].size() <= (int)s[1].size() ){ for( auto x1 : s[0] ){ s[2].insert(x1); } s[0].clear(); } if( (int)s[1].size() + (int)s[2].size() <= (int)s[0].size() ){ for( auto x1 : s[1] ){ s[2].insert(x1); } s[1].clear(); } 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; x = max( x , *(--s[j].end()) ); } 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; }

컴파일 시 표준 에러 (stderr) 메시지

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:123:13: warning: unused variable 'f' [-Wunused-variable]
  123 |         int f = 0;
      |             ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...