oj.uz

Submission #1009186

# Submission time Handle Problem Language Result Execution time Memory
1009186 2024-06-27T09:49:25 Z Khanhcsp2 XOR Sum (info1cup17_xorsum) C++14
100 / 100
 460 ms 25388 KB 
#include<bits/stdc++.h>
#define el '\n'
#define fi first
#define sc second
#define int ll
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
const int mod=1e9+7;
const int N=1e6+11;
int n, a[N], b[N], ans, p1, p2, p3;
void ss(int bit)
{
    for(int i=1;i<=n;i++) b[i]=a[i];
    int id=1;
    while(id<=n)
    {
        if(b[id]>=(1<<(bit+1))) break;
        id++;
    }
    for(int i=id;i<=n;i++) b[i]%=(1<<(bit+1));
    int s1=1, s2=id, run=0;
    while(s1+1<=id && s2<=n)
    {
        if(b[s1]<=b[s2]) a[++run]=b[s1++];
        else a[++run]=b[s2++];
    }
    while(s1+1<=id) a[++run]=b[s1++];
    while(s2<=n) a[++run]=b[s2++];
}
void sol()
{
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    sort(a+1, a+n+1);
    for(int bit=30;bit>=0;bit--)
    {
        ss(bit);
        p1=p2=p3=n+1;
        for(int i=1;i<=n;i++)
        {
//             2^bit <= a[i]+a[p1] <= 2*2^bit-1
//             2*2^bit <= a[i]+a[p2] <= 3*2^bit-1
//             3*2^bit<= a[i]+a[p3] <= 4*2^bit-1
            p1=max(p1, i), p2=max(p2, i), p3=max(p3, i);
            while(i+1<=p1 && 1*(1<<bit)<=a[i]+a[p1-1]) p1--;
            while(i+1<=p2 && 2*(1<<bit)<=a[i]+a[p2-1]) p2--;
            while(i+1<=p3 && 3*(1<<bit)<=a[i]+a[p3-1]) p3--;
            if((n-p1+p2-p3)%2==0) ans=ans^(1<<bit);
        }
    }
    cout << ans;
}
signed main()
{
//    freopen("divisor.INP", "r", stdin);
//    freopen("divisor.OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin >> t;
    while(t--)
    {
        sol();
    }
}

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 20560 KB Output is correct
2 Correct 212 ms 19792 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 20560 KB Output is correct
2 Correct 212 ms 19792 KB Output is correct
3 Correct 302 ms 22600 KB Output is correct
4 Correct 284 ms 22308 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2532 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 47 ms 7708 KB Output is correct
4 Correct 47 ms 7516 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2532 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 232 ms 20560 KB Output is correct
4 Correct 212 ms 19792 KB Output is correct
5 Correct 302 ms 22600 KB Output is correct
6 Correct 284 ms 22308 KB Output is correct
7 Correct 47 ms 7708 KB Output is correct
8 Correct 47 ms 7516 KB Output is correct
9 Correct 421 ms 25228 KB Output is correct
10 Correct 460 ms 25388 KB Output is correct
11 Correct 425 ms 25172 KB Output is correct