oj.uz

Submission #635906

# Submission time Handle Problem Language Result Execution time Memory
635906 2022-08-27T11:00:38 Z Dec0Dedd XOR Sum (info1cup17_xorsum) C++14
77 / 100
 1052 ms 22632 KB 
#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<29; ++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);

      int tmp=0, l=n-1, r=n-1, val=(1<<(b+1))-1, lb=1<<b, ub=(1<<(b+1))-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=(1<<(b+1))+(1<<b), ub=(1<<(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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 6 ms 340 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 641 ms 13152 KB Output is correct
2 Correct 597 ms 16060 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 641 ms 13152 KB Output is correct
2 Correct 597 ms 16060 KB Output is correct
3 Correct 771 ms 19568 KB Output is correct
4 Correct 740 ms 19324 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 6 ms 340 KB Output is correct
3 Correct 107 ms 2552 KB Output is correct
4 Correct 104 ms 2552 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 6 ms 340 KB Output is correct
3 Correct 641 ms 13152 KB Output is correct
4 Correct 597 ms 16060 KB Output is correct
5 Correct 771 ms 19568 KB Output is correct
6 Correct 740 ms 19324 KB Output is correct
7 Correct 107 ms 2552 KB Output is correct
8 Correct 104 ms 2552 KB Output is correct
9 Correct 1052 ms 22616 KB Output is correct
10 Correct 1014 ms 22632 KB Output is correct
11 Incorrect 998 ms 22616 KB Output isn't correct
12 Halted 0 ms 0 KB -