QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#60107#1899. Maximaze XOR sumabdelrahman001#WA 2ms3568kbC++201.3kb2022-11-02 21:13:192022-11-02 21:13:21

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-02 21:13:21]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3568kb
  • [2022-11-02 21:13:19]
  • 提交

answer

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const int N = 1e5 + 5;
int n;
ll a[N], b[N], xr, xr2;
struct gauss {
	vector<pair<ll, int>> setOfXors;
	void ins(ll x, int i) {	///Add X to Gaussian Basis
		for (auto v : setOfXors)
			x = min(x, x ^ v.first);
		if(x)
			setOfXors.push_back({x, i});
	}
	pair<ll, vector<int>> qry(ll x) { ///Get maximum subsequence XOR ^ x
		vector<int> ret;
		for (auto v : setOfXors) {
			if(x ^ v.first > x) {
				x ^= v.first;
				ret.push_back(v.second);
			}
		}
		return {x, ret};
	}
};
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    gauss G;
    cin >> n;
    for(int i = 1;i <= n;i++) {
		cin >> a[i];
		xr ^= a[i];
		xr2 ^= a[i];
	}
	for(int i = 1;i <= n;i++) {
		cin >> b[i];
		xr2 ^= b[i];
		G.ins(a[i] ^ b[i], i);
	}
	auto ret = G.qry(xr);
	cout << ret.first + (xr2 ^ ret.first) << " " << ret.second.size() << '\n';
	for(auto i : ret.second)
		cout << i << " ";
	cout << endl;
    return 0;
}
// xr = xor of all a
// xr2 = xor of all a and b
// c_i = a_i ^ b_i
// query of(xr) = maximum xor for a with the needed swaps
// ans = query of(xr) + (xr2 ^ query of(xr))

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3528kb

input:

2
1 1
2 2

output:

6 1
1 

result:

ok n=2

Test #2:

score: 0
Accepted
time: 2ms
memory: 3568kb

input:

3
2 1 4
4 0 4

output:

7 2
1 2 

result:

ok n=3

Test #3:

score: -100
Wrong Answer
time: 2ms
memory: 3568kb

input:

10
12 0 4 3 1 1 12 3 11 11
3 3 14 6 14 15 1 15 5 2

output:

20 4
1 2 3 6 

result:

wrong answer Jury has better answer