Good Permutation.cpp

#ifdef DEBUG
#include "debug.h"
#endif // DEBUG
#ifndef DEBUG
template <typename T>
void debug(T &x){}
template <typename T>
void debug(T &x, int i, int j){}
#endif // DEBUG

#include <bits/stdc++.h>

using namespace std;

const long long int mod = 1e9 + 7;

long long int getBase(vector <int> &v){
    map <int, int> mp;
    for(int i : v){
        auto res = mp.insert(make_pair(i, 1));
        if(!res.second) res.first->second++;
    }

    long long int res = 1;
    for(auto &p : mp){
        while(p.second){
            res = res * p.second % mod;
            p.second--;
        }
    }

    return res;
}

void setNum(vector <int> &v, int idx){
    if(idx < (int)v.size()) v[(int)v.size() - 1 - idx] = 1;
    else v[idx - (int)v.size()] = 1;
}

int getRealIndex(vector <int> &v, int idx){
    if(idx < (int)v.size()) return (int)v.size() - 1 - idx;
    else return idx - (int)v.size();
}

int getNum(vector <int> &v, int idx){
    if(idx < (int)v.size()) return v[(int)v.size() - 1 - idx];
    else return -v[idx - (int)v.size()];
}

bool allSame(vector <int> &v){
    for(int i : v){
        if(i != v[0]) return false;
    }
    return true;
}

int main(){
    cin.tie(nullptr), ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while(T--){
        int N;
        cin >> N;
        vector <int> A(N), B(N);
        for(int i = 0; i < N; i++) cin >> A[i];
        for(int i = 0; i < N; i++){
            cin >> B[i];
            B[i] = abs(B[i]);
        }

        sort(A.begin(), A.end());
        sort(B.begin(), B.end());

        long long int base = getBase(B);

        int sum = A[0] + getNum(B, 0);
        int idx = 1, ans1 = 0, ans2 = 0;
        vector <int> used(N);
        vector <int> v1(N), v2(N);
        setNum(used, 0);
        v1[0] = getNum(B, 0);

        for(int i = 0; i < 2 * N; i++){
            if(getNum(used, i)) continue;
            if(A[idx] + getNum(B, i) == sum){
                v1[idx] = getNum(B, i);
                idx++, setNum(used, i);
            }
            if(idx == N) break;
        }
        if(idx == N) ans1 = 1;

        sum = A[N - 1] + getNum(B, 2 * N - 1);
        idx = N - 2;
        v2[N - 1] = getNum(B, 2 * N - 1);
        for(int i = 0; i < N; i++) used[i] = 0;
        setNum(used, 2 * N - 1);
        for(int i = 2 * N - 1; i >= 0; i--){
            if(getNum(used, i)) continue;
            if(A[idx] + getNum(B, i) == sum){
                v2[idx] = getNum(B, i);
                idx--, setNum(used, i);
            }
            if(idx == -1) break;
        }
        if(idx == -1) ans2 = 1;

        debug(v1);
        debug(v2);

        bool flag = true;
        for(int i = 0; i < N; i++){
            if(abs(v1[i]) != abs(v2[i])) flag = false;
        }
        if(flag) ans2 = 0;

        long long int ans = base * (ans1 + ans2) % mod;
        cout << ans << "\n";
    }
}