Submission #635907

#	Time	Username	Problem	Language	Result	Execution time	Memory
635907		Dec0Dedd	XOR Sum (info1cup17_xorsum)	C++14	100 / 100	1036 ms	13336 KiB

xorsum

#include <bits/stdc++.h>

using namespace std;

int ans;

int main() {
   int n; cin>>n;
   vector<int> v;
   for (int i=0; i<n; ++i) {
      int a; cin>>a;
      v.push_back(a);
   }

   for (int b=0; b<30; ++b) {
      vector<int> lf, rf;
      for (auto u : v) {
         if (u&(1<<b)) rf.push_back(u);
         else lf.push_back(u);
      }
      v.clear();
      for (auto u : lf) v.push_back(u);
      for (auto u : rf) v.push_back(u);

      long long val=(1ll<<(b+1))-1, lb=1ll<<b, ub=(1ll<<(b+1))-1;
      int tmp=0, l=n-1, r=n-1;
      for (int i=0; i<n; ++i) {
         while (l >= 0 && (v[i]&val)+(v[l]&val) >= lb) --l;
         while (r >= 0 && (v[i]&val)+(v[r]&val) > ub) --r;
         (tmp+=max(0, (r-max(l, i-1))))%=2;
      }

      l=n-1, r=n-1, lb=(1ll<<(b+1))+(1ll<<b), ub=(1ll<<(b+2))-2;
      for (int i=0; i<n; ++i) {
         while (l >= 0 && (v[i]&val)+(v[l]&val) >= lb) --l;
         while (r >= 0 && (v[i]&val)+(v[r]&val) > ub) --r;
         (tmp+=max(0, r-max(l, i-1)))%=2;
      }

      if (tmp) ans^=1<<b;
   }
   cout<<ans<<"\n";
}

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