/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 1ms 532.0 KiB
#3 Accepted 1ms 532.0 KiB
#4 Accepted 5ms 1.062 MiB
#5 Accepted 22ms 5.082 MiB
#6 Accepted 31ms 9.305 MiB
#7 Accepted 26ms 13.27 MiB
#8 Accepted 40ms 20.469 MiB
#9 Accepted 222ms 111.828 MiB
#10 Accepted 415ms 209.453 MiB
#11 Accepted 421ms 209.449 MiB
#12 Accepted 284ms 128.02 MiB
#13 Accepted 509ms 120.367 MiB
#14 Accepted 512ms 120.281 MiB
#15 Accepted 291ms 82.812 MiB
#16 Accepted 180ms 52.004 MiB
#17 Accepted 266ms 90.59 MiB
#18 Accepted 287ms 95.02 MiB
#19 Accepted 278ms 113.242 MiB
#20 Accepted 288ms 126.691 MiB
#21 Accepted 389ms 192.23 MiB

Code

//gpt
#ifndef LOCAL
#include <bits/stdc++.h>
#define debug(...)
#endif

using namespace std;
#define int long long
#define cinv(v) for (auto &it : v) cin >> it;
#define coutv(v) for (auto &it : v) cout << it << ' '; cout << '\n';

const int MX = 30;
const int N  = 300000 + 5;

int a[N];

struct trie {
    int tot;
    trie *a[2];
    trie() : tot(0) {
        a[0] = a[1] = nullptr;
    }
};

trie root;

void insert_x(int x) {
    trie *cur = &root;
    cur->tot++;
    for (int b = MX; ~b; --b) {
        int bit = (x >> b) & 1;
        if (!cur->a[bit]) 
            cur->a[bit] = new trie();
        cur = cur->a[bit];
        cur->tot++;
    }
}

void erase_x(int x) {
    trie *cur = &root;
    cur->tot--;
    for (int b = MX; ~b; --b) {
        int bit = (x >> b) & 1;
        cur = cur->a[bit];
        cur->tot--;
    }
}

int count_greater(int i) {
    // count how many stored x satisfy: (i ^ a[i]) < (i ^ x)
    trie *cur = &root;
    int left = i ^ a[i];
    int cnt = 0;

    for (int b = MX; ~b; --b) {
        if (!cur) break;
        int lb = (left >> b) & 1;   // the bit of (i ^ a[i])
        int ib = (i    >> b) & 1;   // the bit of i
        
        if (lb == 0) {
            // any x whose (i^x)_b == 1 makes the whole number larger
            // (i^x)_b == 1  <=>  x_b == ib^1
            if (cur->a[ib ^ 1])
                cnt += cur->a[ib ^ 1]->tot;
            // then continue down the branch where (i^x)_b == 0
            cur = cur->a[ib];
        } else {
            // left_b == 1, we can only tie & continue if (i^x)_b == 1
            cur = cur->a[ib ^ 1];
        }
    }
    return cnt;
}

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    // reset trie
    root = trie();
    // insert all x_j = j ^ a[j]
    for (int j = 1; j <= n; ++j)
        insert_x(j ^ a[j]);

    long long ans = 0;
    // for each i, remove its own x_i and count how many remaining satisfy
    // (i^a[i]) < (i^x_j)
    for (int i = 1; i <= n; ++i) {
        erase_x(i ^ a[i]);
        ans += count_greater(i);
    }

    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1198 E. Good Signal Pairs
Language
C++17 (G++ 13.2.0)
Submit At
2025-06-24 13:24:45
Judged At
2025-06-24 13:24:45
Judged By
Score
100
Total Time
512ms
Peak Memory
209.453 MiB