fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std ; 
  3.  
  4.  
  5. #define ll long long 
  6. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  7. #define fir first 
  8. #define sec second 
  9. #define piint pair < int , int >
  10. #define FOR( i , a , b ) for (int i = (a) , _b = (b) ; i <= _b ; i ++ )  
  11. #define pb push_back 
  12. #define str string 
  13. #define ALL(a) (a).begin() , (a).end() 
  14. #define rep( i , a , b) for (int i = (a) ; i < (b) ; i ++ )
  15. #define ld long double
  16. const int maxn = 1000;
  17. #define debug 0
  18. #define oo (ll)(1e18)
  19.  
  20.  
  21. void soRT ( vector < pair < ll , ll > >& v ){
  22. 	if ( v.empty()) return;
  23. 	if ( v.size() == 1 ) return ;
  24. 	vector < pair < ll , ll > > v_1 , v_2 ;
  25.  
  26. 	rep ( i , 0 , (int)v.size() ) {
  27. 		if ( v[i].sec & 1 ) {
  28. 			v_1.pb ( { v[i].fir , (v[i].sec + 1)/2 }) ;
  29. 		}
  30. 		else {
  31. 			v_2.pb ( { v[i].fir , v[i].sec /2 }) ;
  32. 		}
  33. 	}
  34. 	soRT ( v_1 ) ;
  35. 	soRT ( v_2 ) ;
  36. 	vector < pair < ll , ll > > neww ;
  37. 	for (auto x : v_1 ) 
  38. 	neww .pb ( {x.fir,x.sec}  );
  39. 	for (auto x : v_2) 
  40. 	neww .pb ( {x.fir,x.sec}) ; 
  41. 	if(debug){
  42. 		for (auto x : neww ) {
  43. 			cerr << "(" << x.fir << "," << x.sec << ")" << ' ' ; 
  44. 		}
  45. 	}
  46. 	v = neww ; 
  47. }
  48.  
  49. // int D_PP[maxn+3] ;
  50. int c[maxn+3] ;
  51. void input(){
  52. 	int n ; cin >> n ;
  53. 	unordered_map < int ,vector < int > > a;
  54.  
  55. 	vector < pair < ll , ll > > v ;
  56.  
  57.  
  58. 	FOR ( i ,1 , n ) {
  59.  
  60. 		int x ; cin >> x;
  61. 		a[x].pb( i ); 
  62.  
  63. 	}
  64. 	FOR ( x , 0 , 1000 ) {
  65. 		if (a[x].size()) v.pb ( { x , x }) ;
  66.  	}
  67.  
  68. 	soRT ( v ) ;
  69.  
  70. 	for (auto x : v ) {
  71. 		if( a[x.fir].size() != 0 ) {
  72. 			for (auto x1: a[x.fir]) {
  73. 				cout << x1 << ' ';
  74. 			}
  75.  
  76. 		}
  77. 	}
  78. 	cout << '\n' ;
  79. }
  80. #define name "TASK" 
  81. int main(){
  82.     fast 
  83.     if(fopen(name".INP","r")) {
  84.         freopen (name".INP","r",stdin);
  85.         freopen (name".OUT","w",stdout);
  86.     }
  87.     int t; cin >> t ;
  88.     while ( t -- ) {
  89.  
  90.     	input();
  91.     }
  92.     cerr << "\nTIME: = " << (1.0*clock())/CLOCKS_PER_SEC << '\n';
  93.     return(0) ;
  94. }
  95.  
Success #stdin #stdout #stderr 3.23s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy
stderr
copy 
TIME: = 3.23442
https://ideone.com/48c7es
language:
C++14 (gcc 8.3)
created:
6 days 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!