QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#111277 | #1899. Maximaze XOR sum | anhduc2701 | WA | 2ms | 5624kb | C++23 | 2.3kb | 2023-06-06 16:20:20 | 2023-06-06 16:20:22 |
Judging History
answer
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI acos(-1.0)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define BIT(x, i) (1 & ((x) >> (i)))
#define MASK(x) (1LL << (x))
#define task "tnc"
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
typedef long long ll;
typedef long double ld;
const ll INF = 1e18;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
const int mo = 998244353;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using pii = pair<pair<ll, ll>, ll>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
int a[maxn];
int b[maxn];
int xo[60];
int p[60];
int q[60];
int s = 0;
int d = 0;
bool add(int x, int id)
{
int su = 0;
for (int i = 59; i >= 0; i--)
{
if ((((1LL << i) & x) == 0) || (((1LL << i) & d)))
continue;
if (p[i] == 0)
{
p[i] = x;
su ^= (1LL << i);
xo[i] = su;
q[i] = id;
return true;
}
else
{
x ^= p[i];
su ^= xo[i];
}
}
return false;
}
pair<int, int> check(int x)
{
int so = 0;
for (int i = 59; i >= 0; i--)
{
if (((1LL << i) & d) || (p[i] == 0) || ((1LL << i) & x))
continue;
x ^= p[i];
so ^= xo[i];
}
return {x, so};
}
signed main()
{
cin.tie(0), cout.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
s ^= a[i];
d ^= a[i];
}
for (int i = 1; i <= n; i++)
{
cin >> b[i];
b[i] ^= a[i];
add(b[i], i);
d ^= b[i];
}
pair<int, int> ans = check(s);
cout << ((d ^ ans.fi) + (ans.fi)) << " ";
int p = ans.se;
cout << __builtin_popcount(ans.se) << "\n";
for (int i = 59; i >= 0; i--)
{
if ((1LL << i) & p)
{
cout << q[i] << " ";
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5496kb
input:
2 1 1 2 2
output:
6 1 1
result:
ok n=2
Test #2:
score: -100
Wrong Answer
time: 2ms
memory: 5624kb
input:
3 2 1 4 4 0 4
output:
14 0
result:
wrong answer Wrong sum