oj.uz

Submission #522751

# Submission time Handle Problem Language Result Execution time Memory
522751 2022-02-05T16:04:44 Z Theo830 XOR Sum (info1cup17_xorsum) C++17
7 / 100
 1600 ms 131076 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 pre[m][n];
    f(j,0,m){
        f(i,0,n){
            pre[j][i] = arr[i] % (1LL<<(j+1));
        }
        sort(pre[j],pre[j] + n);
    }
    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 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[j][l1 - 1] + pre[j][i] >= L1){
                l1--;
            }
            while(l2 > 0 && pre[j][l2 - 1] + pre[j][i] >= L2){
                l2--;
            }
            while(r1 >= 0 && pre[j][r1] + pre[j][i] > R1){
                r1--;
            }
            while(r2 >= 0 && pre[j][r2] + pre[j][i] > R2){
                r2--;
            }
            l1 = max(i,l1);
            l2 = max(i,l2);
            //cout<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<"\n";
            if(r1 >= l1 && pre[j][i] + pre[j][l1] >= L1){
                //cout<<"ev1\n";
                posa[j] += r1 - l1 + 1;
            }
            if(r2 >= l2 && pre[j][i] + pre[j][l2] >= L2){
                //cout<<"ev2\n";
                posa[j] += r2 - l2 + 1;
            }
        }
    }
    f(j,0,m){
        //cout<<posa[j]<<" ";
        ans += (1LL<<j) * (posa[j] % 2);
    }
    cout<<ans<<"\n";
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 1228 KB Output is correct
2 Correct 132 ms 1220 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 114 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 114 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 1228 KB Output is correct
2 Correct 132 ms 1220 KB Output is correct
3 Execution timed out 1616 ms 25392 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 1228 KB Output is correct
2 Correct 132 ms 1220 KB Output is correct
3 Runtime error 114 ms 131076 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -