제출 #522753

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
522753		Theo830	XOR Sum (info1cup17_xorsum)	C++17	45 / 100	1696 ms	15932 KiB

xorsum

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n;
    cin>>n;
    ll arr[n];
    f(i,0,n){
        cin>>arr[i];
    }
    const ll m = 30;
    ll ans = 0;
    ll posa[m] = {0};
    f(j,0,m){
        ///[2^j,2^(j+1) - 1]
        ///[2^(j+1) + 2^j,2^(j+2) - 1]
        ll pre[n];
        f(i,0,n){
            pre[i] = arr[i] % (1LL<<(j+1));
        }
        sort(pre,pre + n);
        ll L1 = (1LL<<j),R1 = (1LL<<(j+1)) - 1;
        ll L2 = (1LL<<j) + (1LL<<(j+1)),R2 = (1LL<<(j+2)) - 1;
        ll l1,r1,l2,r2;
        l1 = l2 = r1 = r2 = n - 1;
        //cout<<j<<": \n";
        //cout<<L1<<" "<<R1<<" "<<L2<<" "<<R2<<"\n";
        f(i,0,n){
            while(l1 > 0 && pre[l1 - 1] + pre[i] >= L1){
                l1--;
            }
            while(l2 > 0 && pre[l2 - 1] + pre[i] >= L2){
                l2--;
            }
            while(r1 >= 0 && pre[r1] + pre[i] > R1){
                r1--;
            }
            while(r2 >= 0 && pre[r2] + pre[i] > R2){
                r2--;
            }
            ll y = l1;
            l1 = max(l1,i);
            ll y2 = l2;
            l2 = max(l2,i);
            //cout<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<"\n";
            if(r1 >= l1 && pre[i] + pre[l1] >= L1){
                //cout<<"ev1\n";
                posa[j] += r1 - l1 + 1;
            }
            if(r2 >= l2 && pre[i] + pre[l2] >= L2){
                //cout<<"ev2\n";
                posa[j] += r2 - l2 + 1;
            }
            l1 = y;
            l2 = y2;
        }
    }
    f(j,0,m){
        //cout<<posa[j]<<" ";
        ans += (1LL<<j) * (posa[j] % 2);
    }
    cout<<ans<<"\n";
}

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