Submission #1116606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116606		12345678	XOR Sum (info1cup17_xorsum)	C++17	100 / 100	512 ms	22712 KiB

xorsum

#include <bits/stdc++.h>

using namespace std;

int n, res;
vector<int> v;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    v.resize(n);
    for (auto &x:v) cin>>x;
    for (int b=1; b<(1<<30); b<<=1)
    {
        vector<int> l, r;
        int cnt=0, idx=0;
        for (auto x:v)
        {
            if (x&b) r.push_back(x);
            else l.push_back(x);
        }
        for (int i=(int)l.size()-1; i>=0; i--)
        {
            while (idx<l.size()&&!((l[i]+l[idx])&b)) idx++;
            if (idx<=i) cnt^=(i-idx+1)%2;
        }
        for (int i=(int)r.size()-1, idx=0; i>=0; i--)
        {
            while (idx<r.size()&&!((r[i]+r[idx])&b)) idx++;
            if (idx<=i) cnt^=(i-idx+1)%2;
        }
        for (int i=(int)l.size()-1, idx=0; i>=0; i--)
        {
            while (idx<r.size()&&(r[idx]+l[i])&b) idx++;
            cnt^=idx%2;
        }
        if (cnt) res|=b;
        v=l;
        for (auto x:r) v.push_back(x);
    }
    cout<<res;
}

Compilation message (stderr)

xorsum.cpp: In function 'int main()':
xorsum.cpp:25:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |             while (idx<l.size()&&!((l[i]+l[idx])&b)) idx++;
      |                    ~~~^~~~~~~~~
xorsum.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |             while (idx<r.size()&&!((r[i]+r[idx])&b)) idx++;
      |                    ~~~^~~~~~~~~
xorsum.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |             while (idx<r.size()&&(r[idx]+l[i])&b) idx++;
      |                    ~~~^~~~~~~~~

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