| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 387803 | RohamIzadidoost | Fun Tour (APIO20_fun) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
//#include "fun.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define pll pair<ll , ll >
#define all(x) (x).begin(),(x).end()
#define SZ(x) (ll)(x).size()
#define X first
#define Y second
#define mp make_pair
#define pii pair<int , int>
#define vec vector
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
// BIG p : 1000000000000037 , 100000000003
ll poww(ll a, ll b, ll md) {
return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}
const int maxn = 1000*100+5 ;
const ll inf = 9223372036854775807 ;
const ll mod = 1e9 + 7 ;
const int lg = 20 ;
pii p ;
int cur , mark[maxn] , n , H[4 * maxn] , val[4 * maxn] , X;
set<pii> seg[4 * maxn] ;
void build(int x = 0 , int lx = 0 , int rx = n , int h = 0 ){
if(rx - lx == 1 && lx < n ){
seg[x].insert({-1 * h , x}) ;
H[x] = h ;
val[x] = lx ;
return ;
}
int mid = lx + rx >> 1 ;
build(x * 2 + 1, lx , mid , h + 1) ;
build(x * 2 + 2 , mid , rx , h + 1) ;
seg[x] = seg[x * 2 + 1] ; for(auto u : seg[x * 2 + 2]) seg[x].insert(u) ;
// sort(all(seg[x])) ;
}
void del(int x){
seg[x].erase({-H[X] , X}) ;
if(x == 0) return ;
x = (x - 1) / 2 ;
del(x) ;
}
pii dfs(int v){
int x , V = v ;;
p = {0 , 0} ;
while(v != 0){
x = v ;
v = (v - 1) / 2 ;
if(x & 1) x = v << 1 ;
else x = v << 1 | 1 ;
if(SZ(seg[x])) p = max(p ,{ H[V] + -1 * (seg[x].begin() -> X) - 2 * H[v] , seg[x].begin() -> Y } ) ;
}
return p ;
}
vec<int> ans ;
vec<int> createFunTour(int N , int Q){
n = N ;
build() ;
ans.pb(seg[1].begin() -> Y) ;
while(SZ(ans) < n){
//cout<<SZ(ans) <<" : " << ans.back() << " -> " << val[ans.back()] << endl ;
X = ans.back() ;
del(ans.back()) ;
ans.pb(dfs(ans.back()).Y) ;
}
for(int i = 0 ; i < n ; i ++ ) ans[i] = val[ans[i]] ;
return ans ;
}
int main()
{
migmig ;
cin>>n ;
build() ;
ans.pb(seg[1].begin() -> Y) ;
while(SZ(ans) < n){
//cout<<SZ(ans) <<" : " << ans.back() << " -> " << val[ans.back()] << endl ;
X = ans.back() ;
del(ans.back()) ;
ans.pb(dfs(ans.back()).Y) ;
}
for(int i = 0 ; i < n ; i ++ ) ans[i] = val[ans[i]] ;
for(auto u : ans) cout<<u <<" " ;
}