結果

問題 No.1240 Or Sum of Xor Pair
ユーザー betrue12betrue12
提出日時 2020-09-26 00:16:03
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,590 bytes
コンパイル時間 2,362 ms
コンパイル使用メモリ 206,620 KB
実行使用メモリ 422,632 KB
最終ジャッジ日時 2023-09-10 17:18:37
合計ジャッジ時間 28,932 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 51 ms
33,100 KB
testcase_04 AC 49 ms
32,556 KB
testcase_05 AC 44 ms
29,252 KB
testcase_06 AC 38 ms
26,268 KB
testcase_07 AC 33 ms
23,000 KB
testcase_08 AC 31 ms
21,880 KB
testcase_09 AC 42 ms
28,488 KB
testcase_10 AC 225 ms
106,676 KB
testcase_11 AC 251 ms
120,504 KB
testcase_12 AC 434 ms
164,620 KB
testcase_13 AC 380 ms
148,996 KB
testcase_14 AC 398 ms
165,528 KB
testcase_15 TLE -
testcase_16 AC 1,790 ms
391,580 KB
testcase_17 AC 1,667 ms
391,576 KB
testcase_18 AC 1,839 ms
391,364 KB
testcase_19 AC 1,690 ms
391,624 KB
testcase_20 AC 1,886 ms
391,904 KB
testcase_21 TLE -
testcase_22 TLE -
testcase_23 AC 1,530 ms
391,724 KB
testcase_24 AC 1,848 ms
391,644 KB
testcase_25 AC 1,274 ms
391,392 KB
testcase_26 AC 1,842 ms
391,476 KB
testcase_27 AC 2 ms
4,384 KB
testcase_28 AC 2 ms
4,380 KB
testcase_29 AC 151 ms
4,380 KB
testcase_30 AC 82 ms
4,380 KB
testcase_31 AC 111 ms
4,380 KB
testcase_32 AC 787 ms
422,632 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