fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define freopen(name) if(fopen(name".INP","r")) {freopen (name".INP","r",stdin); freopen (name".OUT","w",stdout);}
  5. #define fir first
  6. #define sec second
  7. #define str string
  8. const int Max_n=45;
  9. const ll mod=1e9+7;
  10. vector < int > res ;
  11. #define pb push_back 
  12. int n ; 
  13. vector < int > judge [Max_n+3 ];
  14.  
  15. int median ( int i ){
  16. 	vector < int > c = judge[i] ;
  17. 	#define ALL(x) (x).begin() , (x).end()	 
  18. 	sort ( ALL ( c ) )  ;
  19. 	if ( c.size()&1 ) {
  20. 		return c[(c.size() >> 1) ] ;
  21. 	} 
  22. 	else {
  23. 		return ( c[(c.size() >> 1) - 1 ] + c[c.size() / 2 ] ) / 2;
  24. 	}
  25. }
  26. void So ( int k ){
  27. 	if ( k == 2 * n + 1 ) {
  28. 		return ;
  29. 	}
  30. 	if ( judge[k].empty()) return ;
  31. 	if ( k & 1 ){
  32. 		int BASE = median ( k ) ;
  33.  
  34. 		for (auto x : judge[k]) {
  35. 			if ( x > BASE) {
  36. 				res.pb ( k ) ;
  37. 				judge[k+1].pb ( x ) ;
  38. 				// res.pb ( k + 1 );
  39.  
  40. 			}
  41. 			else {
  42. 				res.pb ( k ) ;
  43. 				res.pb (k +1  );
  44.  
  45. 				judge[k+2].pb ( x ) ;
  46. 				// judge[k+2].pb ( x ) ;
  47. 			}
  48. 		}
  49. 		judge[k].clear() ;
  50. 		So ( k + 2 ) ;
  51. 		So ( k + 1 ) ;
  52. 	}
  53. 	else {
  54. 		// cout << k << ' ';
  55. 		for (int i = judge[k].size() - 1 ; i >= 0 ; i -- ) {
  56. 				int x = judge[k][i] ;
  57. 				res.pb ( k ) ;
  58. 				judge[k+1].pb( x ) ;
  59. 		}
  60. 		judge[k].clear() ;
  61. 		So ( k + 1 );
  62.  
  63. 	}
  64. }
  65. int main(){
  66.     freopen("");
  67.     ios_base::sync_with_stdio(0);
  68.     cin.tie(0); cout.tie(0);
  69.     cin >> n ;
  70.     int k ; cin >> k ;
  71.     for (int i= 1 ; i <= k ;i ++  ){
  72.     	int x ; cin >> x ;
  73.     	judge[1].push_back ( x ); 
  74.     }
  75.     So ( 1 ) ;
  76.     cout << res.size() << '\n' ;
  77.     for (auto x : res) cout << x << ' '; 
  78.     return 0;
  79. }//111111111111111111111111
  80.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/h2c8Pw
language:
C++14 (gcc 8.3)
created:
12 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!