QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #561030 | #8077. Alice and Bob | szlhc | WA | 672ms | 6148kb | C++14 | 1.3kb | 2024-09-12 19:39:16 | 2024-09-12 19:39:18 |
Judging History
answer
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
const int N = 5e5 + 5, M = 3.2e7 + 5;
int cas, n, tot, son[M][2], siz[M];
long long a[N], ans;
inline long long C (int x) {return 1ll * x * (x - 1) * (x - 2) / 6;}
void insert (long long x) {
int u = 1;
for (int i = 0; i <= 60; i++) {
int c = ((x >> i) & 1ll);
if (!son[u][c]) son[u][c] = ++tot;
u = son[u][c];
siz[u]++;
}
}
void calc (long long x, long long tmp) {
int u = 1;
for (int i = 0; i <= 2; i++) {
int c = ((x >> i) & 1ll);
if (i % 2 == 0) ans -= tmp * siz[son[u][c ^ 1]];
u = son[u][c];
}
}
int main() {
scanf ("%d", &cas);
while (cas--) {
scanf ("%d", &n);
map <long long, int> mp;
for (int i = 1; i <= n; i++) {
scanf ("%lld", &a[i]);
mp[a[i]]++;
}
ans = C(n);
for (auto it : mp) ans -= C(it.second);
tot = 1;
for (int i = 1; i <= n; i++) insert(a[i]);
for (int i = 1; i <= n; i++) if (mp[a[i]]) {
calc(a[i], 1ll * mp[a[i]] * (mp[a[i]] - 1) / 2);
mp[a[i]] = 0;
}
printf ("%lld\n", ans);
for (int i = 1; i <= tot; i++) siz[i] = 0;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5868kb
input:
3 4 2 0 2 3 3 2 2 3 3 0 2 3
output:
3 0 1
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 672ms
memory: 6148kb
input:
1000000 3 63 98 95 3 61 38 97 3 7 73 98 3 1 10 91 3 94 31 99 3 96 54 97 3 14 44 99 3 81 51 97 3 96 95 92 3 35 90 98 3 7 39 96 3 71 8 96 3 36 35 99 3 82 52 96 3 89 53 99 3 76 85 95 3 80 34 91 3 9 13 99 3 12 17 94 3 40 4 95 3 57 5 93 3 47 69 93 3 23 0 94 3 62 44 97 3 7 4 99 3 21 97 99 3 41 3 99 3 36 9...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -826 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -840 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1918 1 1 1 -1964 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -502 1 1 1 1 1 1 1 -2653 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
result:
wrong answer 36th lines differ - expected: '0', found: '-826'