Submission #7589145


Source Code Expand

Copy
#include <bits/stdc++.h>

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

signed main() {
  ll N;
  cin >> N;
  vector<ull> a(N);

  ull Z = 0;
  rep(i,N){
    cin >> a[i];
    Z ^= a[i];
  }
  rep(i,N){
    a[i] &= ~Z;
  }

  //printf("Z = 0x%x\n", Z);

  // ここで、青色のxorをX、赤色のxorをY、その他をZとする。
  // Zはどのような分割をしても、かならず答えに現れるもの。
  // X+Y+Z = a[0] ^ a[1] ^ ... ^ a[n-1]
  // X ^ Y = 0 --> X = Y
  // なのでa[i]から幾つか選んで、そのxorの合計Xを最大化したい。
  // これを吐き出し法でやっていく。

  ll pivot = 0;
  for (ull bit=(((ull)1) << 63); bit > 0; bit = bit>>1) {
    //printf("bit=0x%lx\n", bit);
    ll t = -1;

    // pivot行を探す
    for (ll i=pivot; i<N; i++) {
      if ((a[i] & bit) != 0) {
        t = i;
        break;
      }
    }

    if (t == -1)
      continue; // そのbitはスキップ

    swap(a[pivot], a[t]);
    rep(i,N) {
      if (i == pivot)
        continue;
      if ((a[i] & bit) != 0) {
        a[i] ^= a[pivot];
      }
    }

    pivot++;
  }

  //rep(i,N){
  //  printf("a[%d]=0x%lx\n", i, a[i]);
  //}

  ull X = 0;
  rep(i,N) {
    X ^= a[i];
  }
  cout << 2*X + Z << endl;
  return 0;
}

Submission Info

Submission Time
Task F - Xor Sum 3
User bobuhiro11
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1485 Byte
Status
Exec Time 92 ms
Memory 1024 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 600 / 600 sample_01.txt, sample_02.txt, sample_03.txt, sub1_01.txt, sub1_02.txt, sub1_03.txt, sub1_04.txt, sub1_05.txt, sub1_06.txt, sub1_07.txt, sub1_08.txt, sub1_09.txt, sub1_10.txt, sub1_11.txt, sub1_12.txt, sub1_13.txt, sub1_14.txt, sub1_15.txt, sub1_16.txt, sub1_17.txt, sub1_18.txt, sub1_19.txt, sub1_20.txt, sub1_21.txt, sub1_22.txt, sub1_23.txt, sub1_24.txt, sub1_25.txt, sub1_26.txt, sub1_27.txt, sub1_28.txt, sub1_29.txt, sub1_30.txt, sub1_small_01.txt, sub1_small_02.txt, sub1_small_03.txt, sub1_small_04.txt, sub1_small_05.txt, sub1_small_06.txt, sub1_small_07.txt, sub1_small_08.txt, sub1_small_09.txt, sub1_small_10.txt, sub1_small_11.txt, sub1_small_12.txt, sub1_small_13.txt, sub1_small_14.txt, sub1_small_15.txt, sub1_small_16.txt, sub1_small_17.txt, sub1_small_18.txt, sub1_small_19.txt, sub1_small_20.txt
Case Name Status Exec Time Memory
sample_01.txt 2 ms 384 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB
sub1_01.txt 28 ms 512 KB
sub1_02.txt 33 ms 640 KB
sub1_03.txt 13 ms 384 KB
sub1_04.txt 52 ms 896 KB
sub1_05.txt 75 ms 1024 KB
sub1_06.txt 77 ms 1024 KB
sub1_07.txt 75 ms 1024 KB
sub1_08.txt 75 ms 1024 KB
sub1_09.txt 75 ms 1024 KB
sub1_10.txt 75 ms 1024 KB
sub1_11.txt 73 ms 1024 KB
sub1_12.txt 77 ms 1024 KB
sub1_13.txt 22 ms 512 KB
sub1_14.txt 67 ms 1024 KB
sub1_15.txt 83 ms 1024 KB
sub1_16.txt 84 ms 1024 KB
sub1_17.txt 84 ms 1024 KB
sub1_18.txt 85 ms 1024 KB
sub1_19.txt 84 ms 1024 KB
sub1_20.txt 86 ms 1024 KB
sub1_21.txt 80 ms 1024 KB
sub1_22.txt 79 ms 1024 KB
sub1_23.txt 81 ms 1024 KB
sub1_24.txt 79 ms 1024 KB
sub1_25.txt 82 ms 1024 KB
sub1_26.txt 92 ms 1024 KB
sub1_27.txt 92 ms 1024 KB
sub1_28.txt 7 ms 512 KB
sub1_29.txt 1 ms 256 KB
sub1_30.txt 21 ms 1024 KB
sub1_small_01.txt 1 ms 256 KB
sub1_small_02.txt 1 ms 256 KB
sub1_small_03.txt 1 ms 256 KB
sub1_small_04.txt 1 ms 256 KB
sub1_small_05.txt 1 ms 256 KB
sub1_small_06.txt 1 ms 256 KB
sub1_small_07.txt 1 ms 256 KB
sub1_small_08.txt 1 ms 256 KB
sub1_small_09.txt 1 ms 256 KB
sub1_small_10.txt 1 ms 256 KB
sub1_small_11.txt 1 ms 256 KB
sub1_small_12.txt 1 ms 256 KB
sub1_small_13.txt 1 ms 256 KB
sub1_small_14.txt 1 ms 256 KB
sub1_small_15.txt 1 ms 256 KB
sub1_small_16.txt 1 ms 256 KB
sub1_small_17.txt 1 ms 256 KB
sub1_small_18.txt 1 ms 256 KB
sub1_small_19.txt 1 ms 256 KB
sub1_small_20.txt 1 ms 256 KB