Submission #387797

#TimeUsernameProblemLanguageResultExecution timeMemory
387797RohamIzadidoostFun Tour (APIO20_fun)C++14
0 / 100
12 ms19020 KiB
#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){ 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){ // cout<<"DELTING " << x << " : " ; seg[x].erase({-H[X] , X}) ; for(auto u : seg[x]) cout<<u.X <<","<<u.Y <<" " ; cout<<endl ; 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> createFunTour(int N , int Q){ n = N ; build() ; vec<int> ans ; 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 <<" " ; }*/

Compilation message (stderr)

fun.cpp: In function 'void build(int, int, int, int)':
fun.cpp:35:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |  int mid = lx + rx >> 1 ;
      |            ~~~^~~~
fun.cpp: In function 'void del(int)':
fun.cpp:44:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   44 |  for(auto u : seg[x]) cout<<u.X <<","<<u.Y <<"  " ; cout<<endl ;
      |  ^~~
fun.cpp:44:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   44 |  for(auto u : seg[x]) cout<<u.X <<","<<u.Y <<"  " ; cout<<endl ;
      |                                                     ^~~~
#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...