c++ - 整数が動揺したとき

Question

私はかなり長い間この問題に悩まされてきました。 https://www.hackerearth.com/code-monk-bit-manipulation/algorithm/when-the-integers-got-upset/ . つまり、長さ N の 2 つの配列 A と P があります。次のように値が計算される 3 番目の配列 Z があります。

Z[i]=(A[i] ^ A[i-1] ^ A[i-2]) times P[i] for i ≥ 2, and 0 otherwise.(^ is exor)

Z の値の合計が最小になるように、A の値を再配置する必要があります。

Eg:A[4]:2 5 4 6
P[4]:1 1 1 1

A の値を :5 6 2 4 のように並べ替えることができます。Z の対応する値は :0 0 1 0 になり、合計は 1 になります。

この問題に対する私のアプローチは O(n!) ですが、時間制限を超えています。動的プログラミングとビットマスキングを使用した O(n^2*2^n) アプローチがあります。

Note:N<=12.
#include <limits.h>
#include <iostream>
#include<algorithm>
using namespace std;


int func(vector<int> a,vector<int> &p)
{
    int res = 0;
//  for(int i=0;i<a.size();i++) cout<<a[i]<<" ";
//  cout<<endl;
    for(int i=2 ; i<a.size() ; i++)
        res += ((a[i-2]^a[i-1]^a[i])*p[i]);
//      cout<<res<<endl;
    return res;
}

int main()
{

    int t ; cin>>t ;
    while(t--)
    {
        int n ; cin>> n;
        vector<int> a(n) , p(n) ;
        for(int i=0;i<n;i++) cin>>a[i];
        for(int i=0;i<n;i++) cin>>p[i];

        sort(a.begin() ,a.end());
        int res = INT_MAX;
        do{

            res = min(res,func(a,p));
        }while(next_permutation(a.begin() , a.end()));

        cout << res << endl;
    }
    return 0;
}