fork download
copy 
  1. //teja349
  2. #include <bits/stdc++.h>
  3. #include <vector>
  4. #include <set>
  5. #include <map>
  6. #include <string>
  7. #include <cstdio>
  8. #include <cstdlib>
  9. #include <climits>
  10. #include <utility>
  11. #include <algorithm>
  12. #include <cmath>
  13. #include <queue>
  14. #include <stack>
  15. #include <iomanip> 
  16. //setbase - cout << setbase (16); cout << 100 << endl; Prints 64
  17. //setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
  18. //setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
  19. //cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
  20.  
  21. using namespace std;
  22. #define f(i,a,b) for(i=a;i<b;i++)
  23. #define rep(i,n) f(i,0,n)
  24. #define fd(i,a,b) for(i=a;i>=b;i--)
  25. #define pb push_back
  26. #define mp make_pair
  27. #define vi vector< int >
  28. #define vl vector< ll >
  29. #define ss second
  30. #define ff first
  31. #define ll long long
  32. #define pii pair< int,int >
  33. #define pll pair< ll,ll >
  34. #define sz(a) a.size()
  35. #define inf (1000*1000*1000+5)
  36. #define all(a) a.begin(),a.end()
  37. #define tri pair<int,pii>
  38. #define vii vector<pii>
  39. #define vll vector<pll>
  40. #define viii vector<tri>
  41. #define mod (1000*1000*1000+7)
  42. #define pqueue priority_queue< int >
  43. #define pdqueue priority_queue< int,vi ,greater< int > >
  44. #define flush fflush(stdout) 
  45. #define primeDEN 727999983
  46. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  47.  
  48. template <typename T>
  49. void printvec(vector<T>& vec){
  50. 	for(int i=0;i<vec.size();i++){
  51. 		cout<<vec[i]<<" ";
  52. 	}
  53. 	cout<<endl;
  54. }
  55.  
  56.  
  57. bool pre[510][500*500+12];
  58. bool suff[510][500*500+12];
  59. int a[512];
  60. int tot=0;
  61. int n;
  62. int getans(int pos){
  63. 	int reqd=tot/2;
  64. 	int i,j=reqd;
  65. 	int wow=0;
  66. 	rep(i,reqd+1){
  67. 		if(!pre[pos-1][i]){
  68. 			continue;
  69. 		}
  70. 		while(j+i>reqd)
  71. 			j--;
  72. 		while(j>=0 && suff[pos+1][j]==0)
  73. 			j--;
  74. 		if(j>=0){
  75. 			wow=max(j+i,wow);
  76. 		}
  77. 	}
  78. 	return wow;
  79. }
  80. int fin[500*500+12],dum[500*500+12],par[500*500+12];
  81. int b[610];
  82. vector<vi> adj(700);
  83. int extractans(int pos){
  84. 	//cout<<pos<<endl;
  85. 	//return 0;
  86. 	int i,j;
  87. 	rep(i,tot+10){
  88. 		fin[i]=0;
  89. 		dum[i]=0;
  90. 		par[i]=0;
  91. 	}
  92. 	//return 0;
  93. 	fin[0]=1;
  94. 	int sumi=1;
  95. 	int elem;
  96. 	f(i,1,n+1){
  97. 		if(i==pos)
  98. 			continue;
  99. 		elem=a[i];
  100. 		rep(j,sumi){
  101. 			if(fin[j])
  102. 				dum[j]=1;
  103. 			if(fin[j] && !fin[j+elem]){
  104. 				dum[j+elem]=1;
  105. 				par[j+elem]=elem;
  106. 			}
  107. 		}
  108. 		sumi+=elem;
  109. 		rep(j,sumi){
  110. 			fin[j]=dum[j];
  111. 		}
  112. 	}
  113. 	tot-=a[pos];
  114. 	int reqd=tot/2;
  115. 	fd(i,reqd,0){
  116. 		if(fin[i])
  117. 			break;
  118. 	}
  119. 	//return 0;
  120.  
  121. 	vi vec1;
  122. 	vi vec2,vec;
  123. 	while(i!=0){
  124. 		vec1.pb(par[i]);
  125. 		//cout<<par[i]<<endl;
  126. 		i=i-par[i];
  127. 	}
  128. 	//return 0;
  129. 	vec1.pb(a[pos]);
  130. 	rep(i,600){
  131. 		b[i]=0;
  132. 	}
  133. 	f(i,1,n+1){
  134. 		b[a[i]]++;
  135. 	}
  136. 	rep(i,vec1.size()){
  137. 		b[vec1[i]]--;
  138. 	}
  139. 	rep(i,600){
  140. 		rep(j,b[i]){
  141. 			vec2.pb(i);
  142. 		}
  143. 	}
  144. 	//return 0;
  145. 	int sum1=0;
  146. 	int sum2=0;
  147. 	i=0;
  148. 	j=0;
  149. 	int cnt=0;
  150. 	while(cnt!=n){
  151. 		if(sum1<=sum2){
  152. 			sum1+=vec1[i];
  153. 			vec.pb(vec1[i]);
  154. 			i++;
  155. 		}
  156. 		else{
  157. 			sum2+=vec2[j];
  158. 			vec.pb(vec2[j]);
  159. 			j++;
  160. 		}
  161. 		cnt++;
  162. 	}
  163. 	//return 0;
  164. 	rep(i,600){
  165. 		b[i]=0;
  166. 	}
  167. 	rep(i,n){
  168. 		//cout<<vec[i]<<endl;
  169. 		b[vec[i]]++;
  170. 		vec[i]=adj[vec[i]][b[vec[i]]-1];
  171. 	}
  172. 	//return 0;
  173. 	rep(i,n){
  174. 		cout<<vec[i]<<" ";
  175. 	}
  176. 	cout<<endl;
  177. 	return 0;
  178. }
  179. int main(){
  180.     std::ios::sync_with_stdio(false); cin.tie(NULL);
  181.     int t;
  182.     cin>>t;
  183.     while(t--){
  184.  
  185.     	cin>>n;
  186.     	int i,j;
  187.     	tot=0;
  188.     	rep(i,600){
  189.     		adj[i].clear();
  190.     	}
  191.     	f(i,1,n+1){
  192.     		cin>>a[i];
  193.     		adj[a[i]].pb(i);
  194.     		tot+=a[i];
  195.     	}
  196.     	rep(i,n+2){
  197.     		rep(j,tot+3){
  198.     			pre[i][j]=0;
  199.     			suff[i][j]=0;
  200.     		}
  201.     	}
  202.     	sort(a+1,a+n+1);
  203.     	pre[0][0]=1;
  204.     	int sumi=1,elem;
  205.     	f(i,1,n+1){
  206.     		elem=a[i];
  207.     		rep(j,sumi){
  208.     			if(pre[i-1][j]){
  209.     				pre[i][j]=1;
  210.     				pre[i][j+elem]=1;
  211.     			}
  212.     		}
  213.     		sumi+=elem;
  214.     	}
  215.     	suff[n+1][0]=1;
  216.     	sumi=1;
  217.     	fd(i,n,1){
  218.     		elem=a[i];
  219.     		rep(j,sumi){
  220.     			if(suff[i+1][j]){
  221.     				suff[i][j]=1;
  222.     				suff[i][j+elem]=1;
  223.     			}
  224.     		}
  225.     		sumi+=elem;
  226.     	}
  227.     	int haha;
  228.     	int maxi=0,posi=0;
  229.     	f(i,1,n+1){
  230.     		tot-=a[i];
  231.     		haha=a[i]+getans(i);
  232.     		tot+=a[i];
  233.     		if(maxi<=haha){
  234.     			maxi=haha;
  235.     			posi=i;
  236.     		}
  237.     	}
  238.     	int wow=a[posi],cnt=0;
  239.     	f(i,posi,n+1){
  240.     		if(wow!=a[i]){
  241.     			wow=a[i];
  242.     			cnt++;
  243.     		}
  244.     	}
  245.     	//cout<<"last coin: "<<a[posi]<<"   cnt of distinct elements greater:  "<<cnt<<endl;
  246.     	//return 0;
  247.     	//cout<<maxi<<endl;
  248.     	extractans(posi);
  249.  
  250.     }
  251.     return 0;   
  252. }
Success #stdin #stdout 0s 267328KB
comments (?)
stdin
copy 
2
4
5 3 20 9
4
2 2 2 2
stdout
copy 
1 4 2 3 
1 2 3 4
https://ideone.com/uyPkB8
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!