QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#86515 | #1899. Maximaze XOR sum | Zuqa# | WA | 2ms | 3456kb | C++17 | 2.3kb | 2023-03-09 23:38:12 | 2023-03-09 23:38:15 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define el '\n'
#define FIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> pt;
typedef unsigned long long ull;
template<typename T, typename X>
using hashTable = gp_hash_table<T, X>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// mt19937_64 for long long
mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());
struct gauss
{
vector<ll> setOfXors;
void ins(ll x)
{ ///Add X to Gaussian Basis
for(auto v: setOfXors)
x = min(x, x ^ v);
if(x)
setOfXors.push_back(x);
}
vector<int> qry(ll x)
{ ///Get maximum subsequence XOR ^ x
vector<int> ret;
for(int i = 0; i < setOfXors.size(); i++)
{
ll v = setOfXors[i];
if((x ^ v) > x)
{
ret.push_back(i);
x = max(x, x ^ v);
}
}
return ret;
}
};
void doWork()
{
int n;
cin >> n;
ll xrA = 0, xrB = 0;
vector<ll> a(n), b(n);
for(int i = 0; i < n; i++)
cin >> a[i], xrA ^= a[i];
for(int i = 0; i < n; i++)
cin >> b[i], xrB ^= b[i];
vector<int> swaps;
ll ans = xrA + xrB;
while(1)
{
gauss g;
for(auto &it: a)
g.ins(it);
auto x = g.qry(0);
for(auto &it: x)
swap(a[it], b[it]);
for(int i = 0; i < n; i++)
xrA ^= a[i], xrB ^= b[i];
if(xrA + xrB > ans)
swaps = x;
else
{
for(auto &it: x)
swap(a[it], b[it]);
break;
}
ans = max(ans, xrA + xrB);
}
cout << ans << ' ' << swaps.size() << '\n';
for(auto &it: swaps)
cout << it + 1;
}
signed main()
{
FIO
int T = 1;
// cin >> T;
for(int i = 1; i <= T; i++)
doWork();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3456kb
input:
2 1 1 2 2
output:
6 1 1
result:
ok n=2
Test #2:
score: -100
Wrong Answer
time: 2ms
memory: 3416kb
input:
3 2 1 4 4 0 4
output:
14 3 123
result:
wrong answer Integer 123 violates the range [1, 3]