Submission #3765824
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define ALL(x) (x).begin(), (x).end()
#define dump(x) cout << (x) << endl
#define LMAX 9223372036854775807LL
#define LMIN -9223372036854775807LL
using ll = long long;
template<typename T>
using vec = vector<T>;
using P = pair<ll, ll>;
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
fill((T *)array, (T *)(array + N), val);
}
const ll INF = 1e16;
const ll MOD = 1e9 + 7;
//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//ll pas[51][52];
signed main(){
IOS;
ll n;
cin >> n;
vec<ll> a(n),b(n),am(n),bm(n);
REP(i,n)cin >> a[i];
REP(i,n)cin >> b[i];
ll ans = 0;
for(ll i = 0;i < 30;i++){
ll mod = (1ll << i + 1);
REP(j, n)am[j] = a[j] % mod;
REP(j, n)bm[j] = b[j] % mod;
sort(ALL(bm));
ll cnt = 0;
ll t = (1ll << i);
REP(j, n){
cnt += lower_bound(ALL(bm),2 * t - am[j]) - lower_bound(ALL(bm),t - am[j]);
cnt += lower_bound(ALL(bm),4 * t - am[j]) - lower_bound(ALL(bm),3 * t - am[j]);
}
if(cnt % 2)ans += (1ll << i);
}
dump(ans);
}
Submission Info
Submission Time |
|
Task |
D - Two Sequences |
User |
jgvt5ti |
Language |
C++14 (GCC 5.4.1) |
Score |
500 |
Code Size |
1246 Byte |
Status |
AC |
Exec Time |
2049 ms |
Memory |
8576 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 |
933 ms |
3456 KB |
N100000_1 |
AC |
933 ms |
3456 KB |
N150000_0 |
AC |
1502 ms |
4992 KB |
N150000_1 |
AC |
1492 ms |
4992 KB |
N200000_0 |
AC |
2049 ms |
8576 KB |
N200000_1 |
AC |
2041 ms |
6528 KB |
N200000_ex_0 |
AC |
1927 ms |
6528 KB |
N200000_ex_1 |
AC |
1924 ms |
6528 KB |
example_0 |
AC |
1 ms |
256 KB |
example_1 |
AC |
1 ms |
256 KB |
example_2 |
AC |
1 ms |
256 KB |
example_3 |
AC |
1 ms |
256 KB |
rand_0 |
AC |
44 ms |
512 KB |
rand_1 |
AC |
98 ms |
640 KB |
smallrand_0 |
AC |
1 ms |
256 KB |
smallrand_1 |
AC |
1 ms |
256 KB |