Submission #205748

#	Time	Username	Problem	Language	Result	Execution time	Memory
205748		CaroLinda	Swap (BOI16_swap)	C++14	100 / 100	953 ms	74232 KiB

swap

#include <bits/stdc++.h>
 
#define debug 
 
const int MAXN = 2e5+10 ;
const int LOG = 30 ;
 
using namespace std ;
 
int N ;
int A[MAXN] ;
int tab[MAXN][LOG] ;
int dp[MAXN][LOG*2] ;
 
char c ;
inline void read(int &num)
{
	num = 0 ; 
	c = getchar() ;
	for(; (c>47 && c < 58) ; c=getchar() )
		num = num*10 + c-48 ;
}
 
inline void fill_tab()
{
 
	for(int i = 1 ; i <= N; i++ )
	{
 
		int anc = i , idx = 0 ;
 
		while( anc )
		{
 
			tab[i][idx] = anc ;
			if( anc<<1 <= N ) tab[i][idx+20] = anc<<1 ;
			anc >>= 1 ;
			idx ++ ;
 
		}
 
	}
 
}
 
int calc_dp(int sub, int anc)
{

	if(sub > N/2 ) return sub ;
 
	int add ;
	int val = A[tab[sub][anc]] ;
 
	if( sub*2 > N ) return add = sub ;
	if( sub*2+1 > N ) return add = ( A[sub*2] < val ) ? sub*2 : sub ;
 
 
 
	if( val < min(A[sub*2], A[sub*2+1]) ) return add = sub ;
	if( A[sub*2] < min(val, A[sub*2+1]) ) return add = calc_dp( sub*2, anc+1 ) ;
 
	int a = val ;
	int b = A[sub*2] ;
	int c = A[sub*2+1] ;
	int val_esq, val_dir ;
 
	if( a < b )
	{
 
		val_esq = calc_dp( sub*2, anc+1 ) ;
		val_dir = calc_dp( sub*2+1, anc+1 ) ;
 
		return add = min( val_esq, val_dir ) ;
 
	}
 
	val_esq = calc_dp( sub*2, 0 ) ;
	val_dir = calc_dp( sub*2+1, 21 ) ;
 
	return add = ( val_esq < val_dir ) ? calc_dp( sub*2+1, anc+1 ) : calc_dp( sub*2, anc+1 ) ;
 
}
 
int main()
{
	read(N) ;
	for(int i = 1 ; i <= N ; i++ ) read(A[i]) ;
 
 
	fill_tab() ;
	memset(dp , -1, sizeof dp ) ;
 
	for(int i = 1 ; i <= N/2 ; i++ )
	{
 
		if( i*2 + 1 > N )
		{
 
			if( i*2 > N || A[i] < A[i*2] ) continue ;
 
			swap( A[i] , A[i*2] ) ;
 
			continue ;
 
		}
 
		//Case 1
		if( A[i] < min( A[i*2] , A[i*2+1] ) ) continue ;
 
		//Case 2
		if( A[i*2] < min( A[i] , A[i*2+1] ) )
		{
			swap( A[i] , A[i*2] ) ;
			continue ;
		}
 
		//Case 3 -> A[i*2+1] < min(A[i] , A[i*2])
		int a = A[i] ;
		int b = A[i*2] ;
		int c = A[i*2+1] ;
		int val_esq, val_dir ;
 
		if( a < b )
		{
 
			val_esq = calc_dp( i*2 , 1 ) ;
			val_dir = calc_dp( i*2+1, 1 ) ;
 
			if( val_esq > val_dir )
				swap(a,b) ;
 
			A[i*2] = a ;
			A[i*2+1] = b ;
 
 
		}
 
		else if( b < a )
		{
 
			val_esq = calc_dp( i*2 , 0 ) ;
			val_dir = calc_dp( i*2+1, 21 ) ;
 
			if( val_esq > val_dir )
				swap(a,b) ;
 
			A[i*2] = b ;
			A[i*2+1] = a;
 
		}
 
		A[i] = c ;
 
	}
 
	for(int i = 1 ; i <= N ; i++  ) printf("%d " , A[i] ) ;
	printf("\n") ;	
 
}

Compilation message (stderr)

swap.cpp: In function 'int calc_dp(int, int)':
swap.cpp:64:6: warning: unused variable 'c' [-Wunused-variable]
  int c = A[sub*2+1] ;
      ^

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