This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
vector<int> v( maxn ), edge( maxn );
int find( int a ){ return (( edge[a] == a ) ? a : edge[a] = find(edge[a])); }
int main(){
int n; cin >> n;
vector<pair<int,int>> ordem;
for( int i = 1; i <= n; i++ ){
cin >> v[i];
edge[i] = i;
if( i > 1 ) ordem.push_back({ v[i], i });
}
sort( ordem.begin(), ordem.end() );
for( auto [val, id] : ordem ){
if( id%2 ){ // filho direito
int a = find(id), b = id/2;
if( a > b ) swap( a, b );
if( v[a] > v[b] ){
swap( v[a], v[b] );
edge[id/2] = id;
}
}
else{
int a = find(id), b = find(id/2);
if( a > b ) swap( a, b );
if( v[a] > v[b] ){
swap( v[a], v[b] );
edge[id/2] = id;
}
}
}
for( int i = 1; i <= n; i++ ) cout << v[i] << " ";
}
# | 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... |