結果

問題 No.1240 Or Sum of Xor Pair
ユーザー betrue12betrue12
提出日時 2020-09-26 00:16:03
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,865 ms / 2,000 ms
コード長 1,590 bytes
コンパイル時間 2,162 ms
コンパイル使用メモリ 207,864 KB
実行使用メモリ 422,784 KB
最終ジャッジ日時 2024-06-28 08:28:12
合計ジャッジ時間 26,144 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 51 ms
33,024 KB
testcase_04 AC 50 ms
32,640 KB
testcase_05 AC 44 ms
29,312 KB
testcase_06 AC 38 ms
26,112 KB
testcase_07 AC 33 ms
23,168 KB
testcase_08 AC 31 ms
22,016 KB
testcase_09 AC 42 ms
28,544 KB
testcase_10 AC 215 ms
106,752 KB
testcase_11 AC 242 ms
120,576 KB
testcase_12 AC 399 ms
164,864 KB
testcase_13 AC 362 ms
149,248 KB
testcase_14 AC 376 ms
165,760 KB
testcase_15 AC 1,839 ms
391,424 KB
testcase_16 AC 1,596 ms
391,808 KB
testcase_17 AC 1,508 ms
391,936 KB
testcase_18 AC 1,679 ms
391,552 KB
testcase_19 AC 1,595 ms
391,808 KB
testcase_20 AC 1,741 ms
392,192 KB
testcase_21 AC 1,810 ms
391,936 KB
testcase_22 AC 1,865 ms
391,680 KB
testcase_23 AC 1,412 ms
391,808 KB
testcase_24 AC 1,679 ms
391,680 KB
testcase_25 AC 1,212 ms
391,680 KB
testcase_26 AC 1,698 ms
391,680 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 2 ms
5,376 KB
testcase_29 AC 155 ms
5,376 KB
testcase_30 AC 83 ms
5,376 KB
testcase_31 AC 114 ms
5,376 KB
testcase_32 AC 811 ms
422,784 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

    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 + (1LL<<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 + (1LL<<(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++){
		cin >> 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