QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#111234 | #1899. Maximaze XOR sum | khanhphucscratch | WA | 3ms | 5584kb | C++14 | 1.3kb | 2023-06-06 13:42:57 | 2023-06-06 13:43:01 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
int basis[60], place[60], a[100001], b[100001], c[100001];
bool getbit(int num, int bit)
{
return (num >> bit)&1;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin>>n;
for(int i = 1; i <= n; i++) cin>>a[i];
for(int i = 1; i <= n; i++) cin>>b[i];
int suma = 0, sumb = 0;
for(int i = 1; i <= n; i++){
suma ^= a[i];
sumb ^= b[i];
c[i] = a[i]^b[i];
}
for(int i = 0; i < 60; i++) basis[i] = -1;
for(int i = 1; i <= n; i++){
for(int j = 59; j >= 0; j--){
if(getbit(c[i], j) == 0) continue;
else if(basis[j] == -1){
basis[j] = c[i];
place[j] = i;
break;
}
else c[i] ^= basis[j];
}
}
vector<int> s;
for(int i = 59; i >= 0; i--){
if(getbit(suma, i) == 1 || getbit(sumb, i) == 1 || basis[i] == -1) continue;
else{
suma ^= basis[i];
sumb ^= basis[i];
s.push_back(place[i]);
}
}
sort(s.begin(), s.end());
cout<<suma+sumb<<" "<<s.size()<<'\n';
for(int i = 0; i < s.size(); i++) cout<<s[i]<<" ";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 5584kb
input:
2 1 1 2 2
output:
6 1 1
result:
ok n=2
Test #2:
score: 0
Accepted
time: 2ms
memory: 3424kb
input:
3 2 1 4 4 0 4
output:
7 0
result:
ok n=3
Test #3:
score: 0
Accepted
time: 2ms
memory: 5528kb
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: 0
Accepted
time: 2ms
memory: 3444kb
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 0
result:
ok n=50
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3420kb
input:
100 50 13 42 41 8 21 50 18 21 50 9 27 51 10 43 26 29 6 52 44 52 19 39 47 59 35 42 6 27 41 8 25 32 32 45 18 57 5 46 32 60 24 63 56 31 32 58 15 0 36 31 33 31 50 14 45 31 27 15 55 8 53 10 5 8 24 15 35 45 34 16 31 44 51 34 13 30 49 0 4 62 6 8 30 44 29 59 60 45 40 1 0 40 29 35 18 42 52 15 28 35 43 24 14 ...
output:
77 1 3
result:
wrong answer Wrong sum