結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0