oj.uz

Submission #1116606

# Submission time Handle Problem Language Result Execution time Memory
1116606 2024-11-22T01:33:43 Z 12345678 XOR Sum (info1cup17_xorsum) C++17
100 / 100
 512 ms 22712 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Output is correct
2 Correct 3 ms 336 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 13292 KB Output is correct
2 Correct 303 ms 16208 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 13292 KB Output is correct
2 Correct 303 ms 16208 KB Output is correct
3 Correct 401 ms 19724 KB Output is correct
4 Correct 359 ms 19468 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 51 ms 2680 KB Output is correct
4 Correct 51 ms 2676 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 331 ms 13292 KB Output is correct
4 Correct 303 ms 16208 KB Output is correct
5 Correct 401 ms 19724 KB Output is correct
6 Correct 359 ms 19468 KB Output is correct
7 Correct 51 ms 2680 KB Output is correct
8 Correct 51 ms 2676 KB Output is correct
9 Correct 490 ms 22712 KB Output is correct
10 Correct 498 ms 22632 KB Output is correct
11 Correct 512 ms 22572 KB Output is correct