Submission #988481

#	Time	Username	Problem	Language	Result	Execution time	Memory
988481		hyakup	Swap (BOI16_swap)	C++17	0 / 100	1 ms	2040 KiB

swap

#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] );
        if( edge[id/2] == id/2 ) edge[id/2] = id;
      }
    }
    else{ // filho esquerdo
      int a = find(id), b = find(id/2);
      if( a > b ) swap( a, b );
      if( v[a] > v[b] ){
        swap( v[a], v[b] );
        if( edge[id/2] == id/2 ) edge[id/2] = id;
      }
    }
  }
  for( int i = 1; i <= n; i++ ) cout << v[i] << " ";
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 11
• Subtask 3: 0 / 27
• Subtask 4: 0 / 20
• Subtask 5: 0 / 32