QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#50720#4446. Link is as bearlqhsmashWA 644ms31440kbC++111.2kb2022-09-28 20:24:352022-09-28 20:24:35

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-28 20:24:35]
  • 评测
  • 测评结果:WA
  • 用时:644ms
  • 内存:31440kb
  • [2022-09-28 20:24:35]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e5 + 50;

int T, n, son[N * 60][2], cnt;
ll a[N];

void insert (ll x) {
    int p = 0;
    for (int i = 60; i >= 0; i --) {
        int v = x >> i & 1;
        if (! son[p][v]) son[p][v] = ++ cnt;
        p = son[p][v];
    }
}

ll query (ll x) {
    ll p = 0, res = 0;
    for (int i = 60; i >= 0; i --) {
        int v = x >> i & 1;
        if (son[p][v ^ 1]) {
            res |= 1ll << i;
            p = son[p][v ^ 1];
        }else p = son[p][v];
    }
    return res;
}

int main() {
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    scanf ("%d", &T);
    while (T --) {
        scanf ("%d", &n);
        for (int i = 1; i <= n; i ++) 
            scanf ("%lld", &a[i]);
        
        insert (0);
        ll ans = 0;
        for (int i = 1; i <= n; i ++) {
            a[i] ^= a[i - 1];
            ans = max (ans, query (a[i]));
            insert (a[i]);
        }
        printf("%lld\n", ans);
        for (int i = 0; i <= cnt; i ++) 
            memset (son[i], 0, sizeof (son[i]));
        cnt = 0;
    }
    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 644ms
memory: 31440kb

input:

22222
100000
595189703884863 72716684812661 449525802123580 504421888022388 390139608591346 108895143840760 170477720052912 185583843894744 201608404318832 128831549357316 521084715261656 668960191579878 573530403227342 489014525501629 56366633717911 1705111713690 227582321537214 710815946393065 169...

output:

1125899906816388
1125899906761715
1125899884349888
1125899831336814
1125899869254854
1125899904711335
1125899875986839
1125899830140053
1125899875195616
1125899906196362
1125899893602740
1125899884704098
1125899868565039
1125899888798079
1125899883647756
1125899879196286
1125899888039962
11258998295...

result:

wrong answer 1st lines differ - expected: '1125899906842623', found: '1125899906816388'