Submission #485727

#TimeUsernameProblemLanguageResultExecution timeMemory
485727ak2006XOR Sum (info1cup17_xorsum)C++14
7 / 100
1685 ms8056 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vb = vector<bool>; using vvb = vector<vb>; using vi = vector<int>; using vvi = vector<vi>; using vl = vector<ll>; using vvl = vector<vl>; using vc = vector<char>; using vvc = vector<vc>; using vs = vector<string>; const ll mod = 1e9 + 7,inf = 1e18; #define pb push_back #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); void setIO() { fast; } int n; bool valid(int l,int r) { return l >= 0 and r <= n - 1 and l <= r; } int main() { setIO(); cin>>n; vi v(n); for (int i = 0;i<n;i++) cin>>v[i]; ll ans = 0; for (int b = 1;b<=30;b++){ vi bits(n); for (int i = 0;i<n;i++){ int x = v[i]; int num = 0; int cnt = 0; vi digs; while (x > 0 and cnt < b){ digs.pb(x%2); x /= 2; cnt++; } reverse(digs.begin(),digs.end()); for (int i = 0;i<digs.size();i++){ int pos = (digs.size() - i - 1); num += digs[i] * (1<<pos); } bits[i] = num; } sort(bits.begin(),bits.end()); //sum of the 2 "b" bit (and hence (b - 1)th position) //numbers should be //in the range //[1<<(b - 1), (1<<b) - 1] //OR //[(1<<b) + (1<<(b - 1)), (1<<(b + 1)) - 2] ll cnt = 0; for (int i = 0;i<n;i++){ int s1 = lower_bound( bits.begin() + i,bits.end(), (1<<(b - 1)) - bits[i]) - bits.begin(); int e1 = -1; int l = i,r = n - 1; while (l <= r){ int mid = (l + r)/2; if (bits[i] + bits[mid] <= (1<<b) - 1){ e1 = mid; l = mid + 1; } else r = mid - 1; } int s2 = lower_bound( bits.begin() + i,bits.end(),-bits[i] + (1<<b) + (1<<(b - 1))) - bits.begin(); int e2 = -1; l = i,r = n - 1; while (l <= r){ int mid = (l + r)/2; if (bits[i] + bits[mid] <= (1<<(b + 1)) - 2){ e2 = mid; l = mid + 1; } else r = mid - 1; } ll num = 0; if (valid(s1,e1) and valid(s2,e2)){ assert(s1 < s2); if (e1 < s2) num = (e1 - s1 + 1) + (e2 - s2 + 1); else num = (e2 - s1 + 1); } else if (valid(s1,e1)) num = e1 - s1 + 1; else if (valid(s2,e2)) num = e2 - s2 + 1; for (int j = s1;j <= e1;j++) assert((bits[i] + bits[j]) & (1<<(b - 1))); for (int j = s2;j <= e2;j++) assert((bits[i] + bits[j]) & (1<<(b - 1))); assert(num >= 0); cnt += num; } if (cnt%2 == 1)ans += (1<<(b - 1)); } cout<<ans<<endl; return 0; }

Compilation message (stderr)

xorsum.cpp: In function 'int main()':
xorsum.cpp:49:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             for (int i = 0;i<digs.size();i++){
      |                            ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...