oj.uz

Submission #522754

# Submission time Handle Problem Language Result Execution time Memory
522754 2022-02-05T16:10:06 Z Theo830 XOR Sum (info1cup17_xorsum) C++17
45 / 100
 1600 ms 15936 KB 
#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;
    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";
        bool ok = 0;
        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";
                ok ^= (r1 - l1 + 1) % 2;
            }
            if(r2 >= l2 && pre[i] + pre[l2] >= L2){
                //cout<<"ev2\n";
                ok ^= (r2 - l2 + 1) % 2;
            }
            l1 = y;
            l2 = y2;
        }
        ans += ok * (1LL<<j);
    }
    cout<<ans<<"\n";
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 332 KB Output is correct
2 Correct 9 ms 332 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1684 ms 15936 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1684 ms 15936 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 332 KB Output is correct
2 Correct 9 ms 332 KB Output is correct
3 Correct 225 ms 1868 KB Output is correct
4 Correct 244 ms 1868 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 332 KB Output is correct
2 Correct 9 ms 332 KB Output is correct
3 Execution timed out 1684 ms 15936 KB Time limit exceeded
4 Halted 0 ms 0 KB -