oj.uz

Submission #988481

# Submission time Handle Problem Language Result Execution time Memory
988481 2024-05-24T20:21:43 Z hyakup Swap (BOI16_swap) C++17
0 / 100
 1 ms 2040 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2040 KB Output isn't correct
2 Halted 0 ms 0 KB -