結果

問題 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  
実行時間 559 ms / 2,000 ms
コード長 1,562 bytes
コンパイル時間 2,998 ms
コンパイル使用メモリ 203,860 KB
実行使用メモリ 72,608 KB
最終ジャッジ日時 2023-09-10 17:19:54
合計ジャッジ時間 10,706 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 11 ms
8,492 KB
testcase_04 AC 10 ms
8,268 KB
testcase_05 AC 10 ms
7,688 KB
testcase_06 AC 8 ms
7,156 KB
testcase_07 AC 7 ms
6,800 KB
testcase_08 AC 8 ms
6,544 KB
testcase_09 AC 10 ms
7,676 KB
testcase_10 AC 50 ms
20,476 KB
testcase_11 AC 59 ms
22,888 KB
testcase_12 AC 104 ms
30,016 KB
testcase_13 AC 89 ms
27,324 KB
testcase_14 AC 98 ms
30,164 KB
testcase_15 AC 559 ms
67,600 KB
testcase_16 AC 502 ms
67,468 KB
testcase_17 AC 473 ms
67,532 KB
testcase_18 AC 502 ms
67,484 KB
testcase_19 AC 470 ms
67,468 KB
testcase_20 AC 532 ms
67,540 KB
testcase_21 AC 535 ms
67,604 KB
testcase_22 AC 551 ms
67,536 KB
testcase_23 AC 458 ms
67,604 KB
testcase_24 AC 520 ms
67,416 KB
testcase_25 AC 344 ms
67,524 KB
testcase_26 AC 537 ms
67,580 KB
testcase_27 AC 1 ms
4,384 KB
testcase_28 AC 1 ms
4,376 KB
testcase_29 AC 144 ms
4,376 KB
testcase_30 AC 76 ms
4,380 KB
testcase_31 AC 98 ms
4,380 KB
testcase_32 AC 258 ms
72,608 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