CF1593D2. Half of Same

题目链接：

Half of Same - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

WA代码：

#include<bits/stdc++.h>
using namespace std;
#define MAX 44
const int N = 2e6+6;
int arr[MAX];
int cnt_1[N];//记录每个数出现的次数
int cnt_2[N];//记录每个因数
int main(){
    int t;cin >> t;
    while(t--){
        int n;cin >> n;
        int ans = 0,pos = 0;
        memset(cnt_1, 0, sizeof(cnt_1));
        memset(arr, 0, sizeof(arr));
        for(int i = 0; i < n; i++){  
            int tmp;cin>>tmp;
            if(cnt_1[tmp+1000000]==0)//不是一样的数
                arr[pos++] = tmp;
            if(++cnt_1[tmp+1000000]>=n/2)//判断是否个数>=n/2
                ans = -1;
        }
        if(pos>2){
            sort(arr,arr+pos);
            for(int i = 0; i < pos - 1; i++){
                int tmp_1;//记录差值
                memset(cnt_2,0,N);
                for(int j = i + 1; j < pos; j++){
                    tmp_1 = arr[j]-arr[i];
                    for(int k = 1; k <= sqrt(tmp_1); k++){
                        if(tmp_1%k==0){
                            cnt_2[k] += cnt_1[arr[j] + 1000000];
                            if(k*k!=tmp_1) 
                            cnt_2[tmp_1/k]+=cnt_1[arr[j]+1000000];
                        }
                    }
                }
                while(cnt_2[tmp_1]<(n/2-cnt_1[arr[i]+1000000])&&tmp_1) tmp_1--;
                ans = max(ans,tmp_1);
            }
        }
        cout<<ans<<endl;
    }
}

测试点信息

46ms/15.30MB
WA
#6
Wrong Answer.wrong answer 2nd numbers differ - expected: '-1', found: '15495'
我初步判断是不是我漏掉了哪种情况但是我看题解没有得出结论。