QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#86514 | #1899. Maximaze XOR sum | Zuqa# | WA | 1ms | 3452kb | C++17 | 2.2kb | 2023-03-09 23:37:14 | 2023-03-09 23:37:19 |
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];
int itr = 0;
vector<int> swaps;
ll ans = xrA + xrB;
while(itr < 50)
{
itr++;
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;
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();
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3356kb
input:
2 1 1 2 2
output:
6 1 1
result:
ok n=2
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3452kb
input:
3 2 1 4 4 0 4
output:
14 3 123
result:
wrong answer Integer 123 violates the range [1, 3]