oj.uz

답안 #1115134

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1115134 2024-11-20T06:27:06 Z 12345678 XOR Sum (info1cup17_xorsum) C++17
7 / 100
 1600 ms 30180 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e6+5;

int n, a[nx], ans;
multiset<int> ms;

struct segtree
{
    struct node
    {
        node *l, *r;
        int sm;
        node(): l(0), r(0), sm(0){}
    };
    typedef node* pnode;
    pnode rt;
    void update(int l, int r, pnode &k, int idx)
    {
        if (!k) k=new node();
        if (l==r) return k->sm++, void();
        int md=(l+r)/2;
        if (idx<=md) update(l, md, k->l, idx);
        else update(md+1, r, k->r, idx);
        k->sm=((k->l)?(k->l->sm):0)+((k->r)?(k->r->sm):0);
        //cout<<"debug "<<l<<' '<<r<<' '<<k->sm<<' '<<idx<<'\n';
    }
    int query(int l, int r, pnode k, int ql, int qr)
    {
        if (!k||qr<l||r<ql) return 0;
        if (ql<=l&&r<=qr) return k->sm;
        int md=(l+r)/2;
        return query(l, md, k->l, ql, qr)+query(md+1, r, k->r, ql, qr);
    }
    void remove(int l, int r, pnode k)
    {
        if (l==r) return free(k), void();
        int md=(l+r)/2;
        if (k->l) remove(l, md, k->l);
        if (k->r) remove(md+1, r, k->r);
        free(k);
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>a[i];
    for (int bit=0; bit<31; bit++)
    {
        ll cur=0, res=0, mod=(1<<(bit+1));
        s.rt=NULL;
        for (int i=1; i<=n; i++)
        {
            s.update(0, mod-1, s.rt, a[i]%mod);
            int l=((((1<<bit)-a[i])%mod)+mod)%mod, r=(l+(1<<bit)-1)%mod;
            if (l<=r) res+=s.query(0, mod-1, s.rt, l, r);
            else res+=s.query(0, mod-1, s.rt, 0, r)+s.query(0, mod-1, s.rt, l, mod-1);
            //cout<<"sm "<<s.rt->sm<<'\n';
            //cout<<"l r "<<l<<' '<<r<<'\n';
            //cout<<"here "<<i<<' '<<res<<'\n';
        }
        s.remove(0, mod-1, s.rt);
        //cout<<res<<'\n';
        if (res%2) ans+=(1<<bit);
    }
    cout<<ans;
}

/*
3
1 2 3
*/

Compilation message

xorsum.cpp: In function 'int main()':
xorsum.cpp:56:12: warning: unused variable 'cur' [-Wunused-variable]
   56 |         ll cur=0, res=0, mod=(1<<(bit+1));
      |            ^~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 2632 KB Output is correct
2 Correct 76 ms 2644 KB Output is correct

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1649 ms 8740 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1649 ms 8740 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 2632 KB Output is correct
2 Correct 76 ms 2644 KB Output is correct
3 Execution timed out 1644 ms 30180 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 2632 KB Output is correct
2 Correct 76 ms 2644 KB Output is correct
3 Execution timed out 1649 ms 8740 KB Time limit exceeded
4 Halted 0 ms 0 KB -