Submission #2860501
Source Code Expand
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <functional>
#include <string>
#include <stack>
#include <set>
#include <sstream>
#include <iomanip>
#include <limits>
#include <cstring>
using namespace std;
using ll = long long;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<string, string> sP;
typedef pair<ll, pair<ll, ll>> PP;
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll INF = 1 << 30;
const ll INF2 = 9e18;
const double INF3 = 9e14;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
const int tx[8] = { -1,0,1,-1,1,-1,0,1 }, ty[8] = { -1,-1,-1,0,0,1,1,1 };
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
#define fr first
#define sc second
int main() {
ll n, a[200010], b[200010], ans = 0;
cin >> n;
for (int i = 0;i < n;i++)cin >> a[i];
for (int i = 0;i < n;i++)cin >> b[i];
for (int i = 0;i <= 28;i++) {
ll c[200010],d[200010];
for (int j = 0;j < n;j++)c[j] = a[j] % (1 << (i + 1));
for (int j = 0;j < n;j++)d[j] = b[j] % (1 << (i + 1));
sort(d, d + n);
ll count1 = 0;
for (int j = 0;j < n;j++) {
int it = lower_bound(d, d + n, (1 << i) - c[j]) - d;
int it2 = lower_bound(d, d + n, (1 << i) * 2 - c[j]) - d;
count1 += max(0, it2 - it);
it = lower_bound(d, d + n, (1 << i) * 3 - c[j]) - d;
it2 = lower_bound(d, d + n, (1 << i) * 4 - c[j]) - d;
count1 += max(0, it2 - it);
}
if (count1 % 2 == 1)ans += 1 << i;
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Two Sequences |
User |
kakakakaneko |
Language |
C++14 (GCC 5.4.1) |
Score |
500 |
Code Size |
1642 Byte |
Status |
AC |
Exec Time |
2053 ms |
Memory |
6528 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
500 / 500 |
Status |
|
|
Set Name |
Test Cases |
Sample |
example_0, example_1, example_2, example_3 |
All |
N100000_0, N100000_1, N150000_0, N150000_1, N200000_0, N200000_1, N200000_ex_0, N200000_ex_1, example_0, example_1, example_2, example_3, rand_0, rand_1, smallrand_0, smallrand_1 |
Case Name |
Status |
Exec Time |
Memory |
N100000_0 |
AC |
937 ms |
5248 KB |
N100000_1 |
AC |
938 ms |
5248 KB |
N150000_0 |
AC |
1512 ms |
6144 KB |
N150000_1 |
AC |
1515 ms |
6016 KB |
N200000_0 |
AC |
2046 ms |
6528 KB |
N200000_1 |
AC |
2053 ms |
6528 KB |
N200000_ex_0 |
AC |
1949 ms |
6528 KB |
N200000_ex_1 |
AC |
1913 ms |
6528 KB |
example_0 |
AC |
2 ms |
4352 KB |
example_1 |
AC |
2 ms |
6400 KB |
example_2 |
AC |
2 ms |
4352 KB |
example_3 |
AC |
2 ms |
4352 KB |
rand_0 |
AC |
46 ms |
4480 KB |
rand_1 |
AC |
103 ms |
4608 KB |
smallrand_0 |
AC |
2 ms |
4352 KB |
smallrand_1 |
AC |
2 ms |
4352 KB |