Submission #287843

#	Time	Username	Problem	Language	Result	Execution time	Memory
287843		nandonathaniel	Swap (BOI16_swap)	C++14	100 / 100	970 ms	3832 KiB

swap

#include<bits/stdc++.h>
using namespace std;

int n,arr[200005];

int cari(int i,int a){
	if(i*2>n)return 0;
	int d=arr[2*i];
	if(i*2+1>n)return d<a;
	int e=arr[2*i+1];
	if(a<d && a<e)return 0;
	if(d<a && d<e)return 1+cari(2*i,a);
	if(a<d){
		return min(cari(2*i,a),cari(2*i+1,a))+1;
	}
	int l1=cari(2*i,d),l2=cari(2*i+1,d);
	if(l1<=l2)return 1+cari(2*i+1,a);
	else return 1+cari(2*i,a);
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin >> n;
	for(int i=1;i<=n;i++)cin >> arr[i];
	arr[n+1]=1e9;
	for(int i=1;2*i<=n;i++){
		int a=arr[i],b=arr[2*i],c=arr[2*i+1];
		if(a<b && a<c)continue;
		if(b<a && b<c){
			swap(arr[i],arr[2*i]);
			continue;
		}
		if(a>b)swap(a,b);
		if(cari(2*i,a)>cari(2*i+1,a))swap(a,b);
		arr[i]=c;
		arr[2*i]=a;
		arr[2*i+1]=b;
	}
	for(int i=1;i<=n;i++){
		cout << arr[i];
		if(i<n)cout << " ";
		else cout << '\n';
	}
	return 0;
}

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