Submission #3240347


Source Code Expand

#include <cstdio>
#include <algorithm>

using namespace std;
using ll = long long;

int search(const ll n[], int len, ll comp) {
  int i = 0;
  int j = len;
  while (i < j) {
    int h = (i + j) >> 1;
    if (n[h] < comp) i = h + 1;
    else j = h;
  }
  return i;
}

int main() {
  int n;
  scanf("%d", &n);

  int tmpa[n], tmpb[n];
  for (int i = 0; i < n; i++) scanf("%d", &tmpa[i]);
  for (int i = 0; i < n; i++) scanf("%d", &tmpb[i]);

  ll ans = 0;
  for (int bit = 0; bit < 29; bit++) {
    ll t = 1 << bit;
    ll a[n], b[n];
    for (int i = 0; i < n; i++) {
      a[i] = tmpa[i] % (2 * t);
      b[i] = tmpb[i] % (2 * t);
    }
    sort(b, b + n);

    int c = 0;
    for (int i = 0; i < n; i++) {
      int c1 = search(b, n, t - a[i]);
      int c2 = search(b, n, 2 * t - a[i]);
      int c3 = search(b, n, 3 * t - a[i]);
      int c4 = search(b, n, 4 * t - a[i]);
      c = (c + c2 - c1 + c4 - c3) % 2;
    }

    if (c == 1) ans += t;
  }

  printf("%lld\n", ans);
  return 0;
}

Submission Info

Submission Time
Task D - Two Sequences
User icewaterGreentea
Language C++14 (Clang 3.8.0)
Score 500
Code Size 1042 Byte
Status AC
Exec Time 2460 ms
Memory 4992 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 4
AC × 16
Set Name Test Cases
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
Case Name Status Exec Time Memory
N100000_0 AC 1088 ms 2560 KB
N100000_1 AC 1088 ms 2560 KB
N150000_0 AC 1768 ms 3712 KB
N150000_1 AC 1783 ms 3712 KB
N200000_0 AC 2460 ms 4992 KB
N200000_1 AC 2458 ms 4992 KB
N200000_ex_0 AC 2347 ms 4992 KB
N200000_ex_1 AC 2354 ms 4992 KB
example_0 AC 1 ms 256 KB
example_1 AC 1 ms 256 KB
example_2 AC 1 ms 256 KB
example_3 AC 1 ms 256 KB
rand_0 AC 44 ms 384 KB
rand_1 AC 100 ms 512 KB
smallrand_0 AC 1 ms 256 KB
smallrand_1 AC 1 ms 256 KB