oj.uz

Submission #205748

# Submission time Handle Problem Language Result Execution time Memory
205748 2020-02-29T17:57:12 Z CaroLinda Swap (BOI16_swap) C++14
100 / 100
 953 ms 74232 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47220 KB Output is correct
2 Correct 34 ms 47352 KB Output is correct
3 Correct 31 ms 47224 KB Output is correct
4 Correct 32 ms 47352 KB Output is correct
5 Correct 31 ms 47224 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47220 KB Output is correct
2 Correct 34 ms 47352 KB Output is correct
3 Correct 31 ms 47224 KB Output is correct
4 Correct 32 ms 47352 KB Output is correct
5 Correct 31 ms 47224 KB Output is correct
6 Correct 37 ms 47224 KB Output is correct
7 Correct 35 ms 47608 KB Output is correct
8 Correct 31 ms 47352 KB Output is correct
9 Correct 31 ms 47352 KB Output is correct
10 Correct 31 ms 47352 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47220 KB Output is correct
2 Correct 34 ms 47352 KB Output is correct
3 Correct 31 ms 47224 KB Output is correct
4 Correct 32 ms 47352 KB Output is correct
5 Correct 31 ms 47224 KB Output is correct
6 Correct 37 ms 47224 KB Output is correct
7 Correct 35 ms 47608 KB Output is correct
8 Correct 31 ms 47352 KB Output is correct
9 Correct 31 ms 47352 KB Output is correct
10 Correct 31 ms 47352 KB Output is correct
11 Correct 31 ms 47352 KB Output is correct
12 Correct 32 ms 47224 KB Output is correct
13 Correct 34 ms 47480 KB Output is correct
14 Correct 32 ms 47480 KB Output is correct
15 Correct 31 ms 47352 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47220 KB Output is correct
2 Correct 34 ms 47352 KB Output is correct
3 Correct 31 ms 47224 KB Output is correct
4 Correct 32 ms 47352 KB Output is correct
5 Correct 31 ms 47224 KB Output is correct
6 Correct 37 ms 47224 KB Output is correct
7 Correct 35 ms 47608 KB Output is correct
8 Correct 31 ms 47352 KB Output is correct
9 Correct 31 ms 47352 KB Output is correct
10 Correct 31 ms 47352 KB Output is correct
11 Correct 31 ms 47352 KB Output is correct
12 Correct 32 ms 47224 KB Output is correct
13 Correct 34 ms 47480 KB Output is correct
14 Correct 32 ms 47480 KB Output is correct
15 Correct 31 ms 47352 KB Output is correct
16 Correct 44 ms 53880 KB Output is correct
17 Correct 45 ms 53880 KB Output is correct
18 Correct 45 ms 53884 KB Output is correct
19 Correct 141 ms 53880 KB Output is correct
20 Correct 138 ms 54008 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47220 KB Output is correct
2 Correct 34 ms 47352 KB Output is correct
3 Correct 31 ms 47224 KB Output is correct
4 Correct 32 ms 47352 KB Output is correct
5 Correct 31 ms 47224 KB Output is correct
6 Correct 37 ms 47224 KB Output is correct
7 Correct 35 ms 47608 KB Output is correct
8 Correct 31 ms 47352 KB Output is correct
9 Correct 31 ms 47352 KB Output is correct
10 Correct 31 ms 47352 KB Output is correct
11 Correct 31 ms 47352 KB Output is correct
12 Correct 32 ms 47224 KB Output is correct
13 Correct 34 ms 47480 KB Output is correct
14 Correct 32 ms 47480 KB Output is correct
15 Correct 31 ms 47352 KB Output is correct
16 Correct 44 ms 53880 KB Output is correct
17 Correct 45 ms 53880 KB Output is correct
18 Correct 45 ms 53884 KB Output is correct
19 Correct 141 ms 53880 KB Output is correct
20 Correct 138 ms 54008 KB Output is correct
21 Correct 86 ms 74104 KB Output is correct
22 Correct 93 ms 74196 KB Output is correct
23 Correct 89 ms 74104 KB Output is correct
24 Correct 953 ms 74232 KB Output is correct
25 Correct 936 ms 74232 KB Output is correct