1343D - Constant Palindrome Sum - CodeForces Solution

#include <bits/stdc++.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

#define repi(i, a, b) for (int i = (a), i##len = (b); i <= i##len; ++i)
#define repll(i, a, b) for (ll i = (a), i##len = (b); i <= i##len; ++i)
#define peri(i, a, b) for (int i = (a), i##len = (b); i >= i##len; --i)
#define perll(i, a, b) for (ll i = (a), i##len = (b); i >= i##len; --i)
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define cg \
  repi(i, 1, n) { g[i].clear(); }
#define x first
#define y second
#define all(x) x.begin(), x.end()
// #define sz(x) (x).size()
#define lowbit(t) t & (-t)
#define PI 3.1415926535
#define INF 0x3f3f3f3f
const ll MOD = 1e9 + 7;
int dx[8] = {-1, 0, 1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
template <class U, class T>
void Max(U &x, T y) {
  if (x < y) x = y;
}
template <class U, class T>
void Min(U &x, T y) {
  if (x > y) x = y;
}

template <typename T>
inline void rd(T &x) {
  x = 0;
  int w = 1;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') w = -1;
    c = getchar();
  }
  while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
  x *= w;
}

template <typename T>
inline void wt(T x) {
  static int a[65];
  int top = 0;
  do {
    a[top++] = x % 10, x /= 10;
  } while (x);
  while (top) putchar(a[--top] + 48);  // 48 是 '0'
}

int dcmp(double a, double b) {
  constexpr double eps = 1e-9;
  if (a - b < eps) return -1;
  if (a - b > eps) return 1;
  return 0;
}

struct int128 {
  long long hig;
  long long low;
};
// if(ans.hig==0) {
//         printf("%lld", ans.low);
//     } else {
//         printf("%lld%018lld\n", ans.hig, ans.low);
//     }
// ll p = 1e18;  //作mod用
// int128 max(int128 a, int128 b) {
//   if (a.hig > b.hig) return a;
//   if (a.hig < b.hig) return b;  //高位比较
//   if (a.low > b.low) return a;
//   if (a.low < b.low) return b;  //低位比较
//   return a;                     //相等时还要返回一个值
// }
// int128 operator+(int128 a, int128 b)  //重载运算符
// {
//   int128 k;
//   k.low = 0, k.hig = 0;
//   k.low = a.low + b.low;
//   k.hig = k.low / p + a.hig + b.hig;  //防止溢出
//   k.low %= p;
//   return k;
// }
// int128 operator*(int128 a, int b) {
//   int128 k;
//   k.low = 0, k.hig = 0;
//   k.low = a.low * b;
//   k.hig += k.low / p + b * a.hig;  //与上同理
//   k.low %= p;
//   return k;
// }

vector<int> mul_vec(const vector<int> &a, int b) {
  vector<int> c;
  int t = 0;
  for (int i = 0; i < a.size(); i++) {
    t += a[i] * b;
    c.push_back(t % 10);
    t /= 10;
  }
  while (t) {
    c.push_back(t % 10);
    t /= 10;
  }
  return c;
}

vector<int> div_vec(const vector<int> &a, int b) {
  vector<int> c;
  bool is_first = true;
  for (int i = a.size() - 1, t = 0; i >= 0; i--) {
    t = t * 10 + a[i];
    int x = t / b;
    if (!is_first || x) {
      is_first = false;
      c.push_back(x);
    }
    t %= b;
  }
  reverse(c.begin(), c.end());
  return c;
}

vector<int> max_vec(const vector<int> &a, const vector<int> &b) {
  if (a.size() > b.size()) return a;
  if (a.size() < b.size()) return b;
  if (vector<int>(a.rbegin(), a.rend()) > vector<int>(b.rbegin(), b.rend()))
    return a;
  return b;
}

void print_vec(const vector<int> &a) {
  for (int i = a.size() - 1; i >= 0; i--) {
    printf("%d", a[i]);
  }
}

inline ll qpow(ll b, ll k, int MOD) {
  ll ans = 1;
  while (k) {
    if (k & 1) {
      (ans *= b) %= MOD;
    }
    (b *= b) %= MOD;
    k >>= 1;
  }
  return ans;
}

int n, m, k;
constexpr int MAXN = 4e5 + 5;
vi g[MAXN];
int a[MAXN];
int cnt[MAXN];

void solve() {
  rd(n);
  rd(k);
  repi(i,1,n) {
    rd(a[i]);
  }
  repi(i,2,2*k) {
    cnt[i] = 0;
  }
  repi(i,1,n/2) {
    int cur = a[i]+a[n-i+1];
    int mn1 = min(a[i],a[n-i+1])+1;
    int mx1 = max(a[i],a[n-i+1])+k;
    cnt[2]+=2;
    --cnt[mn1];
    --cnt[cur];
    ++cnt[cur+1];
    ++cnt[mx1+1];
  }
  int ans = n;
  repi(i,2,2*k) {
    cnt[i]+=cnt[i-1];
    Min(ans, cnt[i]);
  }
  wt(ans);
  puts("");
}

int main(int argc, char **argv) {
#ifndef ONLINE_JUDGE
  freopen("in.txt", "r", stdin);
#endif
  int T = 1;
  rd(T);
  while (T--) {
    solve();
  }
  return 0;
}