結果

問題 No.1240 Or Sum of Xor Pair
ユーザー betrue12betrue12
提出日時 2020-09-26 00:20:14
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 733 ms / 2,000 ms
コード長 1,562 bytes
コンパイル時間 2,193 ms
コンパイル使用メモリ 204,412 KB
実行使用メモリ 72,832 KB
最終ジャッジ日時 2024-06-28 08:29:09
合計ジャッジ時間 12,471 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 12 ms
8,448 KB
testcase_04 AC 12 ms
8,320 KB
testcase_05 AC 10 ms
7,808 KB
testcase_06 AC 9 ms
7,296 KB
testcase_07 AC 8 ms
6,944 KB
testcase_08 AC 7 ms
6,944 KB
testcase_09 AC 10 ms
7,552 KB
testcase_10 AC 55 ms
20,608 KB
testcase_11 AC 64 ms
22,912 KB
testcase_12 AC 113 ms
30,208 KB
testcase_13 AC 100 ms
27,520 KB
testcase_14 AC 110 ms
30,208 KB
testcase_15 AC 629 ms
67,584 KB
testcase_16 AC 579 ms
67,840 KB
testcase_17 AC 551 ms
67,840 KB
testcase_18 AC 605 ms
67,584 KB
testcase_19 AC 551 ms
67,840 KB
testcase_20 AC 639 ms
67,712 KB
testcase_21 AC 640 ms
67,840 KB
testcase_22 AC 633 ms
67,712 KB
testcase_23 AC 526 ms
67,840 KB
testcase_24 AC 620 ms
67,840 KB
testcase_25 AC 398 ms
67,712 KB
testcase_26 AC 733 ms
67,712 KB
testcase_27 AC 2 ms
6,944 KB
testcase_28 AC 2 ms
6,944 KB
testcase_29 AC 144 ms
6,944 KB
testcase_30 AC 77 ms
6,940 KB
testcase_31 AC 99 ms
6,940 KB
testcase_32 AC 271 ms
72,832 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
 
struct BinaryTrie{
    int nth_bit(int x, int n){ return (x>>n) & 1; }

    struct Node{
        Node* ch[2];
		int num[18][2];
        Node(){
			ch[0] = ch[1] = nullptr;
			memset(num, 0, sizeof(num));
		}
    };

    int B;
    Node* root;

    BinaryTrie(int B=0){ if(B) initialize(B); }
    void initialize(int inB){
        B = inB;
        root = new Node();
    }

    void insert(Node* node, int x, int depth){
		for(int k=0; k<18; k++) node->num[k][nth_bit(x, k)]++;
        if(depth < B){
            int nextdepth = depth + 1;
            int nextbit = nth_bit(x, B - nextdepth);
            if(!node->ch[nextbit]) node->ch[nextbit] = new Node();
            insert(node->ch[nextbit], x, nextdepth);
        }
    }
    void insert(int x){ insert(root, x, 0); }

	void calc(Node* node, int x, int now, int K, int X, int64_t& ans){
		if(!node) return;
		int mn = now, mx = now + (1<<K) - 1;
		if(mn >= X) return;
		if(mx < X){
			for(int k=0; k<18; k++) for(int t=0; t<2; t++) ans += node->num[k][t] * (1LL<<k) * (nth_bit(x, k) | t);
			return;
		}
		if(K > 0) for(int t=0; t<2; t++) calc(node->ch[t], x, now + (1<<(K-1)) * (nth_bit(x, K-1) ^ t), K-1, X, ans);
	}

	void calc(int x, int X, int64_t& ans){ return calc(root, x, 0, B, X, ans); }
};
 
int main(){
	int N, X;
	cin >> N >> X;
	BinaryTrie bt(18);
	vector<int> A(N);
	for(int i=0; i<N; i++){
		scanf("%d", &A[i]);
		bt.insert(A[i]);
	}

	int64_t ans = 0;
	for(int a : A){
		ans -= a;
		bt.calc(a, X, ans);
	}
	ans /= 2;
	cout << ans << endl;
}
0