結果

問題 No.2977 Kth Xor Pair
ユーザー 👑 ygussany
提出日時 2024-12-01 01:06:27
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 1,971 ms / 3,000 ms
コード長 2,806 bytes
コンパイル時間 2,333 ms
コンパイル使用メモリ 32,580 KB
実行使用メモリ 10,512 KB
最終ジャッジ日時 2024-12-01 01:07:16
合計ジャッジ時間 43,735 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>

int bit[31];

long long count2(int N1, int N2, int A1[], int A2[], int m)
{
	if (m == 0 || N1 == 0 || N2 == 0) return (long long)N1 * N2;
	
	int i, j1, j2, k, kk;
	for (k = 30; k >= 0; k--) {
		for (i = 1, j1 = 0; i <= N1 && j1 != 3; i++) {
			if ((A1[i] & bit[k]) != 0) j1 |= 1;
			else j1 |= 2;
		}
		for (i = 1, j2 = 0; i <= N2 && j2 != 3; i++) {
			if ((A2[i] & bit[k]) != 0) j2 |= 1;
			else j2 |= 2;
		}
		if ((j1 | j2) == 3) break;
	}
	for (kk = 30; kk >= 0; kk--) if ((m & bit[kk]) != 0) break;
	if (kk > k) return 0;
	
	int N11 = 0, N12 = 0, N21 = 0, N22 = 0, *A11, *A12, *A21, *A22;
	A11 = (int*)malloc(sizeof(int) * (N1 + 1));
	A12 = (int*)malloc(sizeof(int) * (N1 + 1));
	A21 = (int*)malloc(sizeof(int) * (N2 + 1));
	A22 = (int*)malloc(sizeof(int) * (N2 + 1));
	for (i = 1; i <= N1; i++) {
		if ((A1[i] & bit[k]) != 0) A11[++N11] = A1[i] ^ bit[k];
		else A12[++N12] = A1[i];
	}
	for (i = 1; i <= N2; i++) {
		if ((A2[i] & bit[k]) != 0) A21[++N21] = A2[i] ^ bit[k];
		else A22[++N22] = A2[i];
	}
	A11 = (int*)realloc(A11, sizeof(int) * (N11 + 1));
	A12 = (int*)realloc(A12, sizeof(int) * (N12 + 1));
	A21 = (int*)realloc(A21, sizeof(int) * (N21 + 1));
	A22 = (int*)realloc(A22, sizeof(int) * (N22 + 1));

	long long ans;
	if (k > kk) ans = (long long)N11 * N22 + (long long)N12 * N21 + count2(N11, N21, A11, A21, m) + count2(N12, N22, A12, A22, m);
	else ans = count2(N11, N22, A11, A22, m ^ bit[k]) + count2(N12, N21, A12, A21, m ^ bit[k]);
	free(A11);
	free(A12);
	free(A21);
	free(A22);
	return ans;
}

long long count(int N, int A[], int m)
{
	if (m == 0) return (long long)N * (N - 1) / 2;
	
	int i, j, k, kk;
	for (k = 30; k >= 0; k--) {
		for (i = 1, j = 0; i <= N && j != 3; i++) {
			if ((A[i] & bit[k]) != 0) j |= 1;
			else j |= 2;
		}
		if (j == 3) break;
	}
	for (kk = 30; kk >= 0; kk--) if ((m & bit[kk]) != 0) break;
	if (kk > k) return 0;
	
	int N1 = 0, N2 = 0, *A1, *A2;
	A1 = (int*)malloc(sizeof(int) * (N + 1));
	A2 = (int*)malloc(sizeof(int) * (N + 1));
	for (i = 1; i <= N; i++) {
		if ((A[i] & bit[k]) != 0) A1[++N1] = A[i] ^ bit[k];
		else A2[++N2] = A[i];
	}
	A1 = (int*)realloc(A1, sizeof(int) * (N1 + 1));
	A2 = (int*)realloc(A2, sizeof(int) * (N2 + 1));

	long long ans;
	if (k > kk) ans = (long long)N1 * N2 + count(N1, A1, m) + count(N2, A2, m);
	else ans = count2(N1, N2, A1, A2, m ^ bit[k]);
	free(A1);
	free(A2);
	return ans;
}

int main()
{
	int i, N, A[200001];
	long long K;
	scanf("%d %lld", &N, &K);
	for (i = 1; i <= N; i++) scanf("%d", &(A[i]));
	for (i = 1, bit[0] = 1; i <= 30; i++) bit[i] = bit[i-1] << 1;
	
	int l = 0, r = bit[30] - 1, m;
	while (l < r) {
		m = (l + r + 1) / 2;
		if (count(N, A, m) <= (long long)N * (N - 1) / 2 - K) r = m - 1;
		else l = m;
	}
	printf("%d\n", l);
	fflush(stdout);
	return 0;
}
0