fork download
copy 
  1. #include<bits/stdc++.h>                   // below comment for pbds
  2. #include<ext/pb_ds/assoc_container.hpp>   // to use it make ordered_set
  3. #include<ext/pb_ds/tree_policy.hpp>       // all set fnct + = 1. order_of_key(x); //number 
  4. #define ll long long                      //of element strictly smaller than it;
  5. #define ld long double                    // 2. find_by_order(x),pointer el at x pos after sort use as s.f();
  6. #define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
  7. using namespace std;                 
  8. using namespace __gnu_pbds;
  9.  
  10.  
  11.  
  12. int main()
  13. {
  14. 	ios_base::sync_with_stdio(false);
  15. 	cin.tie(NULL);
  16. 	cout.flush();
  17. 	ll t=1;
  18. 	cin>>t;
  19. 	while(t--)
  20. 	{
  21. 	ll n,k;
  22. 	cin>>n>>k;
  23. 	ll a[200001];
  24. 	for(ll i=1;i<=n;i++)
  25. 	{
  26. 		cin>>a[i];
  27. 		}
  28. 	ll ans=0;	
  29. 	ll In[200002];
  30. 	ll Ins[200001];
  31. 	ll S[200001];
  32. 	memset(S,0,sizeof(S));
  33. 	memset(Ins,0,sizeof(Ins));
  34. 	memset(In,0,sizeof(In));
  35. 	for(ll i=1;i<=n;i++)
  36. 	{
  37. 		Ins[a[i]]++;
  38. 		In[a[i]]++;
  39. 	}
  40.  
  41. 	for(ll i=1;i<=n/2;i++)
  42. 	{
  43. 	ll s= a[i]+a[n-i+1];	
  44. 	S[s]++;
  45. 	}
  46. 	for(ll i=200000;i>=0 ;i--)
  47. 	{
  48. 	In[i]=In[i+1]+In[i]; // largerequal top  sum i;		
  49. 	}
  50.  
  51. 	for(ll i=1;i<=200000;i++)
  52. 	{
  53. 	Ins[i]=Ins[i-1]+Ins[i]; // smaller than or equal top  sum i;		
  54. 	}
  55.  
  56. 	ll A;
  57. 	ans = LLONG_MAX;
  58. 	for(ll i=1;i<=n/2;i++)
  59. 	{
  60. 		ll s = a[i]+a[n-i+1];
  61.  
  62. 		 A = n-(S[s]*2);
  63. 		 A=A/2;
  64.  
  65. 		 ll p = s - k;
  66.  
  67. 		 if(p-1>=0)  
  68. 		 A = A + Ins[p-1];
  69.  
  70. 		 ll xx = s;
  71. 		if(xx>0)
  72. 		 A=A+ In[xx] ;
  73.  
  74. 		 ans = min(ans,A)	;
  75. 	//	 cout<<"A: "<<A<<endl;
  76. 	}
  77.  
  78.  
  79.  
  80. 	cout<<ans<<endl;
  81. 	}
  82.  
  83. return 0;
  84. }
  85.  
  86.  
Success #stdin #stdout 0s 8164KB
comments (?)
stdin
copy 
1
8 7
6 1 1 7 6 3 4 6
stdout
copy 
7
https://ideone.com/9I7GlV
language:
C++ (gcc 8.3)
created:
3 years 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!