QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#86447 | #1899. Maximaze XOR sum | triplem5ds# | WA | 2ms | 3476kb | C++20 | 2.2kb | 2023-03-09 21:48:45 | 2023-03-09 21:48:49 |
Judging History
answer
///Enta etfsh5t nseet el rank
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
tree_order_statistics_node_update>;
#define pb push_back
#define F first
#define S second
#define f(i, a, b) for (int i = a; i < b; i++)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(x) (int)(x).size()
//#define mp(x, y) make_pair(x, y)
#define popCnt(x) (__builtin_popcountll(x))
#define int ll
using ll = long long;
using ull = unsigned long long;
using uint = uint32_t;
using ii = pair<int, int>;
const int N = 3e6 + 6, A = 26, LG = 18, MOD = (119 << 23) + 1;
const long double PI = acos(-1);
const long double EPS = 1e-9;
const ll INF = 1e15;
int val = 0;
vector<tuple<int, int, bitset<64>>> vec;
void ins(int x, int i) {
bitset<64> bt2;
for (auto [v, i, bt]: vec) {
if ((v ^ x) < x) {
bt2 ^= bt;
x ^= v;
}
}
if (x) {
bt2[vec.size()] = 1;
vec.push_back({x, i, bt2});
}
}
void doWork() {
int n;
cin >> n;
vector<int> a(n), b(n);
f(i, 0, n) {
cin >> a[i];
val ^= a[i];
}
f(i, 0, n) {
cin >> b[i];
val ^= b[i];
}
f(i, 0, n) {
a[i] ^= (a[i] & val);
b[i] ^= (b[i] & val);
ins(a[i] ^ b[i], i);
}
int ans = 0;
bitset<64> res;
for (auto [v, i, bt]: vec) {
if ((ans ^ v) > ans) {
res ^= bt;
ans ^= v;
}
}
cout << ans * 2 + val << ' ' << res.count() << '\n';
f(i, 0, 64) if (res[i])cout << get<1>(vec[i]) + 1 << ' ';
}
int32_t main() {
#ifdef ONLINE_JUDGE
ios_base::sync_with_stdio(0);
cin.tie(0);
#endif // ONLINE_JUDGE
int t = 1;
// cin >> t;
while (t--)
doWork();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3368kb
input:
2 1 1 2 2
output:
6 1 1
result:
ok n=2
Test #2:
score: 0
Accepted
time: 2ms
memory: 3476kb
input:
3 2 1 4 4 0 4
output:
7 0
result:
ok n=3
Test #3:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
10 12 0 4 3 1 1 12 3 11 11 3 3 14 6 14 15 1 15 5 2
output:
26 1 1
result:
ok n=10
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3476kb
input:
50 9 27 19 1 31 10 2 7 25 26 12 25 15 18 11 15 30 25 31 2 5 30 8 18 8 17 14 2 17 7 26 26 10 25 26 5 3 5 1 17 18 12 4 17 14 19 30 30 20 2 13 18 3 8 18 11 31 20 21 14 17 29 31 2 5 28 31 17 10 13 6 10 22 18 10 2 0 15 7 14 4 15 25 10 3 30 3 21 0 12 11 19 4 16 27 10 26 3 2 5
output:
35 1 1
result:
wrong answer Wrong sum