提出 #3238778

ソースコード 拡げる

#include <iostream>
#include <algorithm>

#define N_MAX 200000

long a[N_MAX];
long b[N_MAX];
long b_rem_sort[28][N_MAX];

using namespace std;

int main(){
    int N;
    int xors[N_MAX] = {0};
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> a[i];
    }
    for(int i = 0; i < N; i++){
        cin >> b[i];
        long pow2 = 1;
        for(int j = 0; j < 28; j++){
            pow2 *= 2;
            b_rem_sort[j][i] = b[i]%pow2;
        }
    }
    for(int j = 0; j < 28; j++){
        sort(b_rem_sort[j], b_rem_sort[j] + N);
    }

    long pow2 = 1;
    for(int j = 0; j < 28; j++){
        pow2 *= 2;
        for(int i = 0; i < N; i++){
            int bound1, bound2, bound3;
            long a_rem;
            a_rem = a[i]%pow2;
            bound1 = lower_bound(b_rem_sort[j], b_rem_sort[j] + N, pow2/2 - a_rem) - b_rem_sort[j];
            bound2 = lower_bound(b_rem_sort[j], b_rem_sort[j] + N, pow2 - a_rem) - b_rem_sort[j];
            bound3 = lower_bound(b_rem_sort[j], b_rem_sort[j] + N, pow2/2 + pow2 - a_rem) - b_rem_sort[j];
            xors[j] = (xors[j] + bound2 - bound1 + N - bound3)%2;
        }
        //cout << '\n';
    }

    long ret = 0;
    pow2 = 1;
    for(int j = 0; j < 28; j++){
        ret += xors[j]*pow2;
        pow2 *= 2;
    }
    cout << ret << '\n';

}

提出情報

提出日時
問題 D - Two Sequences
ユーザ ytkn
言語 C++14 (Clang 3.8.0)
得点 0
コード長 1363 Byte
結果 WA
実行時間 2108 ms
メモリ 47872 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 0 / 500
結果
AC × 4
AC × 12
WA × 4
セット名 テストケース
Sample example_0, example_1, example_2, example_3
All N100000_0, N100000_1, N150000_0, N150000_1, N200000_0, N200000_1, N200000_ex_0, N200000_ex_1, example_0, example_1, example_2, example_3, rand_0, rand_1, smallrand_0, smallrand_1
ケース名 結果 実行時間 メモリ
N100000_0 AC 986 ms 46208 KiB
N100000_1 WA 988 ms 46080 KiB
N150000_0 AC 1546 ms 46848 KiB
N150000_1 WA 1547 ms 46848 KiB
N200000_0 AC 2108 ms 47872 KiB
N200000_1 WA 2106 ms 47872 KiB
N200000_ex_0 AC 1979 ms 47872 KiB
N200000_ex_1 AC 1980 ms 47872 KiB
example_0 AC 9 ms 44032 KiB
example_1 AC 10 ms 44032 KiB
example_2 AC 9 ms 44032 KiB
example_3 AC 9 ms 44032 KiB
rand_0 AC 60 ms 44160 KiB
rand_1 WA 119 ms 44416 KiB
smallrand_0 AC 9 ms 44032 KiB
smallrand_1 AC 9 ms 44032 KiB