QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#401799#7411. Bitwise Xorjames1BadCreeper#WA 1ms7772kbC++141.3kb2024-04-29 13:54:552024-04-29 13:54:55

Judging History

你现在查看的是最新测评结果

  • [2024-04-29 13:54:55]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7772kb
  • [2024-04-29 13:54:55]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 
const int P = 998244353; 
const int N = 3e5 + 5; 

int n; 
i64 a[N], x; 

int ch[N * 61][2], tot, sz[N * 61]; 

void insert(i64 val, int ad) {
    int p = 1; sz[1] = (sz[1] + ad) % P; 
    for (int i = 59; i >= 0; --i) {
        int c = val >> i & 1; 
        if (!ch[p][c]) ch[p][c] = ++tot; 
        p = ch[p][c]; sz[p] = (sz[p] + ad) % P;
    }
}
int query(int p, int dep, i64 val) {
    if (p == 0) return 0; 
    if (dep == 0) return sz[p]; 

    int pv = val >> dep - 1 & 1, px = x >> dep - 1 & 1, ans = 0; 
    // 选择 0 
    if (pv > px) ans = (ans + sz[ch[p][0]]) % P; 
    else if (pv == px) ans = (ans + query(ch[p][0], dep - 1, val)) % P; 

    if ((pv ^ 1) > px) ans = (ans + sz[ch[p][1]]) % P; 
    else if ((pv ^ 1) == px) ans = (ans + query(ch[p][1], dep - 1, val)) % P; 

    return ans; 
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> x; tot = 1; 
    for (int i = 1; i <= n; ++i) cin >> a[i]; 
    sort(a + 1, a + n + 1); 
    
    int ans = 0; 
    for (int i = 1; i <= n; ++i) {
        int val = (query(1, 60, a[i]) + 1) % P; 
        cout << val << "\n"; 
        ans = (ans + val) % P; 
        insert(a[i], val); 
    }
    cout << ans << "\n"; 
    return 0;
}

// 相邻

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 7772kb

input:

3 0
0 1 2

output:

1
2
4
7

result:

wrong answer 1st numbers differ - expected: '7', found: '1'