QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#60110#1899. Maximaze XOR sumabdelrahman001#WA 2ms3716kbC++201.4kb2022-11-02 21:22:242022-11-02 21:22:25

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:22:25]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3716kb
  • [2022-11-02 21:22:24]
  • 提交

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, ll xr2) { ///Get maximum subsequence XOR ^ x
		vector<int> ret;
		for (auto v : setOfXors) {
			ll nxt = x ^ v.first;
			if(nxt + (nxt ^ xr2) > x + (xr2 ^ 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, xr2);
	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))

详细

Test #1:

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

input:

2
1 1
2 2

output:

6 1
1 

result:

ok n=2

Test #2:

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

input:

3
2 1 4
4 0 4

output:

7 0


result:

ok n=3

Test #3:

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

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: 3716kb

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: 2ms
memory: 3628kb

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 2
2 6 

result:

wrong answer Wrong sum