fork download
  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
stdin
1
8 7
6 1 1 7 6 3 4 6
stdout
7