제출 #1318652

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318652		TraianDanciu	XOR Sum (info1cup17_xorsum)	C++20	100 / 100	1159 ms	12160 KiB

xorsum

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

const int MAXN = 1000000;

int v[MAXN + 1], ord[MAXN + 1], neword[MAXN + 1];

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n;
  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> v[i];
    ord[i] = i;
  }

  sort(ord + 1, ord + n + 1, [&](int a, int b) {
    return v[a] < v[b];
  });

  int answer = 0;
  for(int bit = 29; bit >= 0; bit--) {
    int ptr1 = n, ptr2 = n, ptr3 = n, ptr4 = n;
    long long nrsecv = 0;
    for(int i = 1; i <= n; i++) {
      while(ptr1 >= i && v[ord[i]] + v[ord[ptr1]] >= (1LL << bit)) {
        ptr1--;
      }
      while(ptr2 >= i && v[ord[i]] + v[ord[ptr2]] >= (2LL << bit)) {
        ptr2--;
      }
      while(ptr3 >= i && v[ord[i]] + v[ord[ptr3]] >= (3LL << bit)) {
        ptr3--;
      }
      while(ptr4 >= i && v[ord[i]] + v[ord[ptr4]] >= (4LL << bit)) {
        ptr4--;
      }
      nrsecv += max(0, ptr4 - i + 1) - max(0, ptr3 - i + 1) + max(0, ptr2 - i + 1) - max(0, ptr1 - i + 1);
    }

    if(nrsecv % 2) {
      answer += (1 << bit);
    }

    if(bit > 0) {
      int i = 1;
      while(i <= n && v[ord[i]] < (1 << bit)) {
        i++;
      }
      for(int j = i; j <= n; j++) {
        v[ord[j]] -= (1 << bit);
      }

      int x = 1, y = i, ptr = 0;
      while(x < i && y <= n) {
        if(v[ord[x]] < v[ord[y]]) {
          neword[++ptr] = ord[x++];
        } else {
          neword[++ptr] = ord[y++];
        }
      }
      while(x < i) {
        neword[++ptr] = ord[x++];
      }
      while(y <= n) {
        neword[++ptr] = ord[y++];
      }

      for(int i = 1; i <= n; i++) {
        ord[i] = neword[i];
      }
    }
  }

  cout << answer << "\n";
  return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 38 / 38
• Subtask 5: 23 / 23