Submission #4161815


Source Code Expand

Copy
#include <bits/stdc++.h>
#define REP(i, a, n) for (ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;

int main(void) {
  ll N, K;
  cin >> N >> K;
  vector<ll> A(N);
  REP(i, 0, N) cin >> A[i];

  vector<ll> b;
  while (K > 0) {
    b.push_back(K % 2);
    K /= 2;
  }
  while (b.size() < 60) {
    b.push_back(0);
  }

  vector<ll> cnt0(60), cnt1(60);
  REP(k, 0, 60) {
    REP(i, 0, N) {
      if ((A[i] & (1LL << k)) == 0) {
        cnt0[k]++;
      } else {
        cnt1[k]++;
      }
    }
  }

  ll ans = 0;
  REP(i, 0, b.size()) {
    if (b[i] == 0) {
      ans += (1LL << i) * cnt1[i];
    } else {
      ans += (1LL << i) * cnt0[i];
    }
  }

  for (ll k = (ll) b.size() - 1; k >= 0; k--) {
    if (b[k] == 1) {
      ll p = 0;
      for (ll i = (ll) b.size() - 1; i > k; i--) {
        if (b[i] == 0) {
          p += (1LL << i) * cnt1[i];
        } else {
          p += (1LL << i) * cnt0[i];
        }
      }

      p += (1LL << k) * cnt1[k];

      for (ll i = k - 1; i >= 0; i--) {
        p += (1LL << i) * max(cnt0[i], cnt1[i]);
      }

      ans = max(ans, p);
    }
  }

  cout << ans << endl;
}

Submission Info

Submission Time
Task D - XXOR
User kshinya
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1207 Byte
Status
Exec Time 71 ms
Memory 1024 KB

Judge Result

Set Name Score / Max Score Test Cases
All 400 / 400 0_normal_1, 0_normal_2, 0_normal_3, 0_normal_4, 0_normal_5, 0_normal_6, 0_normal_7, 0_normal_8, 0_normal_9, 1_max_1, 1_max_2, 1_max_3, 1_max_4, 1_max_5, 1_max_6, 1_max_7, 1_max_8, 2_beki_1, 2_beki_2, 3_hand_1, 3_hand_2, 3_hand_3, sample_01, sample_02, sample_03
Sample 0 / 0 sample_01, sample_02, sample_03
Case Name Status Exec Time Memory
0_normal_1 44 ms 768 KB
0_normal_2 7 ms 256 KB
0_normal_3 53 ms 768 KB
0_normal_4 31 ms 512 KB
0_normal_5 43 ms 640 KB
0_normal_6 55 ms 896 KB
0_normal_7 58 ms 896 KB
0_normal_8 56 ms 896 KB
0_normal_9 36 ms 640 KB
1_max_1 71 ms 1024 KB
1_max_2 71 ms 1024 KB
1_max_3 71 ms 1024 KB
1_max_4 71 ms 1024 KB
1_max_5 71 ms 1024 KB
1_max_6 71 ms 1024 KB
1_max_7 71 ms 1024 KB
1_max_8 71 ms 1024 KB
2_beki_1 58 ms 896 KB
2_beki_2 55 ms 896 KB
3_hand_1 66 ms 1024 KB
3_hand_2 45 ms 1024 KB
3_hand_3 62 ms 1024 KB
sample_01 1 ms 256 KB
sample_02 1 ms 256 KB
sample_03 1 ms 256 KB