結果

問題 No.1456 Range Xor
ユーザー ethan_hethan_h
提出日時 2021-03-31 21:19:04
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,362 bytes
コンパイル時間 2,045 ms
コンパイル使用メモリ 169,428 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-05-09 04:43:43
合計ジャッジ時間 9,993 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 WA -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 AC 2 ms
5,376 KB
testcase_44 AC 3 ms
5,376 KB
testcase_45 AC 2 ms
5,376 KB
testcase_46 AC 2 ms
5,376 KB
testcase_47 AC 2 ms
5,376 KB
testcase_48 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

//ethan_h
#include<bits/stdc++.h>
using namespace std;
#define ll long long
/*void test(){
int n;cin>>n;
string s;cin>>s;
vector<int>a(n);
for(int i=0;i<n;i++){
cin>>a[i];}

}
*/
int subsetXOR(vector<int>arr, int n, int k)
{
    // Find maximum element in arr[]
    int max_ele = arr[0];
    for (int i=1; i<n; i++)
       if (arr[i] > max_ele)
           max_ele = arr[i];

    // Maximum possible XOR value
    int m = (1 << (int)(log2(max_ele) + 1) ) - 1;
    if( k > m  )
       return 0;
    // The value of dp[i][j] is the number of subsets having
    // XOR of their elements as j from the set arr[0...i-1]
    int dp[n+1][m+1];

    // Initializing all the values of dp[i][j] as 0
    for (int i=0; i<=n; i++)
        for (int j=0; j<=m; j++)
            dp[i][j] = 0;

    // The xor of empty subset is 0
    dp[0][0] = 1;

    // Fill the dp table
    for (int i=1; i<=n; i++)
        for (int j=0; j<=m; j++)
            dp[i][j] = dp[i-1][j] + dp[i-1][j^arr[i-1]];

    //  The answer is the number of subset from set
    //  arr[0..n-1] having XOR of elements as k
    return dp[n][k];
}
int main(){
ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

//int t;cin>>t;
int n,k;cin>>n>>k;
vector<int>a(n);
for(int i=0;i<n;i++){
    cin>>a[i];
}
int res;
res=subsetXOR(a,n,k);
if(res>0){
    cout<<"Yes";
}
else{
    cout<<"No";
}
return 0;}
0