模拟退火后三点WA 已经交了一页多了

#include<bits/stdc++.h>

#define int long long
#define down 0.912

using namespace std;

int t,n,mid;
int a[1000],s1,s2,ans,odd;

int read(){
    int w = 1, q = 0;
    char ch = ' ';
    while(ch != '-' && (ch < '0' || ch > '9'))ch = getchar();
    if(ch == '-')w = -1, ch = getchar();
    while(ch >= '0' && ch <= '9')q = q * 10 + ch - '0', ch = getchar();
    return w * q;
}

void sa(){
	double te = 4649;
	while(te > 1e-10){
		int x = (int)(rand()) % mid + 1;
		int y = n - (int)(rand()) % (mid + odd);
		int dis = abs(s1 - a[x] * 2 + a[y] * 2 - s2);
		double d = dis - ans;
		if(d < 0){
			ans = dis;
			s1 = s1 - a[x] + a[y];
			s2 = s2 - a[y] + a[x];
			swap(a[x],a[y]);
		}
		else if(exp((d / te)) < rand() % 32768){
			s1 = s1 - a[x] + a[y];
			s2 = s2 - a[y] + a[x];
			swap(a[x],a[y]);
		}
		te *= down;
	}
}

signed main(){
	srand(time(0));
	cin>>t;
	while(t --){
		n = read();
		mid = n / 2;
		odd = n % 2;
		s1 = s2 = 0;
		for(int i = 1;i <= n;i ++){
			a[i] = read();
			if(i <= mid)s1 += a[i];
			else s2 += a[i];
		}
		if(n == 1){
			cout<<a[1];
			continue;
		}
		ans = abs(s1 - s2);
		for(int i = 1;i <= 667;i ++)sa();
  		printf("%d\n",ans);
	}
	return 0;
}

为了挽救蒟蒻的生命，请高抬贵手帮助一下我