10551 | 2024-04-05 12:32:24 | CWM | Xorzótábla | cpp17 | Time limit exceeded 14/100 | 2.099s | 6168 KiB |
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;
long long cMod = 2;
int bitlookahead = 1;
bool comp(int a, int b) {
a = a % cMod;
b = b % cMod;
return b > a;
}
signed main()
{
int sA, sB;
cin >> sA >> sB;
vector<int> a(sA);
vector<int> b(sB);
for (size_t i = 0; i < sA; i++)
{
cin >> a[i];
}
for (size_t i = 0; i < sB; i++)
{
cin >> b[i];
}
long long res = 0;
while (cMod<4e9)
{
sort(a.begin(), a.end(), comp);
sort(b.begin(), b.end(), comp);
vector<int> aTemp(sA);
vector<int> bTemp(sB);
for (size_t i = 0; i < sA; i++)
{
aTemp[i] = a[i] % cMod;
}
for (size_t i = 0; i < sB; i++)
{
bTemp[i] = b[i] % cMod;
}
long long lLim = cMod / 2;
long long uLim = cMod;
int ans = 0;
for (size_t i = 0; i < aTemp.size(); i++)
{
int lIdx = lower_bound(bTemp.begin(), bTemp.end(), lLim - aTemp[i]) - bTemp.begin();
int uIdx = lower_bound(bTemp.begin(), bTemp.end(), uLim - aTemp[i]) - bTemp.begin();
int ulIdx = lower_bound(bTemp.begin(), bTemp.end(), uLim+lLim - aTemp[i]) - bTemp.begin();
int cDif = uIdx - lIdx + bTemp.size()-ulIdx;
ans += cDif;
}
if (ans % 2 == 1) {
res += cMod;
}
cMod *= 2;
bitlookahead++;
}
cout << res/2;
return 0;
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 3ms | 1808 KiB | ||||
2 | Time limit exceeded | 2.099s | 2716 KiB | ||||
subtask2 | 14/14 | ||||||
3 | Accepted | 3ms | 2164 KiB | ||||
4 | Accepted | 14ms | 2320 KiB | ||||
5 | Accepted | 14ms | 2520 KiB | ||||
6 | Accepted | 8ms | 2728 KiB | ||||
7 | Accepted | 23ms | 2704 KiB | ||||
8 | Accepted | 21ms | 2756 KiB | ||||
9 | Accepted | 29ms | 2876 KiB | ||||
subtask3 | 0/14 | ||||||
10 | Accepted | 4ms | 2996 KiB | ||||
11 | Time limit exceeded | 2.099s | 4136 KiB | ||||
12 | Time limit exceeded | 2.099s | 4156 KiB | ||||
13 | Time limit exceeded | 2.029s | 4456 KiB | ||||
14 | Time limit exceeded | 2.065s | 4632 KiB | ||||
subtask4 | 0/14 | ||||||
15 | Time limit exceeded | 2.065s | 4012 KiB | ||||
16 | Time limit exceeded | 2.053s | 4320 KiB | ||||
17 | Time limit exceeded | 2.066s | 4400 KiB | ||||
18 | Time limit exceeded | 2.015s | 4916 KiB | ||||
19 | Time limit exceeded | 2.062s | 4944 KiB | ||||
subtask5 | 0/21 | ||||||
20 | Accepted | 527ms | 4892 KiB | ||||
21 | Accepted | 1.794s | 6168 KiB | ||||
22 | Time limit exceeded | 2.075s | 4900 KiB | ||||
23 | Time limit exceeded | 2.065s | 4976 KiB | ||||
24 | Time limit exceeded | 2.042s | 5128 KiB | ||||
25 | Time limit exceeded | 2.073s | 5144 KiB | ||||
subtask6 | 0/37 | ||||||
26 | Accepted | 261ms | 4556 KiB | ||||
27 | Time limit exceeded | 2.066s | 4540 KiB | ||||
28 | Time limit exceeded | 2.062s | 4712 KiB | ||||
29 | Time limit exceeded | 2.049s | 4912 KiB | ||||
30 | Time limit exceeded | 2.042s | 5072 KiB | ||||
31 | Time limit exceeded | 2.049s | 5176 KiB | ||||
32 | Time limit exceeded | 2.073s | 5244 KiB | ||||
33 | Time limit exceeded | 2.069s | 5216 KiB | ||||
34 | Time limit exceeded | 2.058s | 5208 KiB |