Submission #66798149

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 200009
int n,sum,x[N],b[66];
void add(int x){
	for(int p = 60;p >= 0;p--){
		if((x & (1ll << p)) == 0) continue;
		if(!b[p]){
			b[p] = x;
			return;
		}
		x ^= b[p];
	}
}
void upd(){
	for(int p = 60;p >= 0;p--){
		if(!b[p]) continue;
		for(int q = p - 1;q >= 0;q--)
			if((b[p] & (1ll << q))) b[p] ^= b[q];
	}
}
signed main(){
	cin.tie(0); cout.tie(0);
	ios::sync_with_stdio(0);
	cin>>n;
	if(n <= 20){
		for(int i = 1;i <= n;i++) cin>>x[i],sum ^= x[i];
		int ans = 0;
		for(int i = 0;i < (1 << n);i++){
			int res = 0;
			for(int j = 0;j < n;j++)
				if(i & (1 << j)) res ^= x[j + 1];
			//cout<<i<<":"<<res<<" "<<(sum ^ res)<<" "<<res + (sum ^ res)<<endl;
			ans = max(ans,res + (sum ^ res));
		}
		cout<<ans<<endl;
	}else{
		for(int i = 1;i <= n;i++){
			cin>>x[i];
			add(x[i]);
			sum ^= x[i];
		}
		upd();
		int mx = 0;
		for(int i = 0;i <= 60;i++) mx ^= b[i];
		int ans = mx + (mx ^ sum);
		for(int i = 0;i <= 60;i++){
			int now = (mx ^ b[i]);
			ans = max(ans,now + (now ^ sum));
		}
		cout<<ans<<endl;
	}
	return 0;
}

Submission Info

Submission Time
Task F - Xor Sum 3
User eastgeorge
Language C++ 20 (gcc 12.2)
Score 600
Code Size 1158 Byte
Status AC
Exec Time 62 ms
Memory 4404 KiB

Judge Result

Set Name Sample Subtask1
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 53
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 sample_01.txt, sample_02.txt, sample_03.txt, sub1_01.txt, sub1_02.txt, sub1_03.txt, sub1_04.txt, sub1_05.txt, sub1_06.txt, sub1_07.txt, sub1_08.txt, sub1_09.txt, sub1_10.txt, sub1_11.txt, sub1_12.txt, sub1_13.txt, sub1_14.txt, sub1_15.txt, sub1_16.txt, sub1_17.txt, sub1_18.txt, sub1_19.txt, sub1_20.txt, sub1_21.txt, sub1_22.txt, sub1_23.txt, sub1_24.txt, sub1_25.txt, sub1_26.txt, sub1_27.txt, sub1_28.txt, sub1_29.txt, sub1_30.txt, sub1_small_01.txt, sub1_small_02.txt, sub1_small_03.txt, sub1_small_04.txt, sub1_small_05.txt, sub1_small_06.txt, sub1_small_07.txt, sub1_small_08.txt, sub1_small_09.txt, sub1_small_10.txt, sub1_small_11.txt, sub1_small_12.txt, sub1_small_13.txt, sub1_small_14.txt, sub1_small_15.txt, sub1_small_16.txt, sub1_small_17.txt, sub1_small_18.txt, sub1_small_19.txt, sub1_small_20.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 3656 KiB
sample_02.txt AC 1 ms 3540 KiB
sample_03.txt AC 62 ms 3420 KiB
sub1_01.txt AC 5 ms 3804 KiB
sub1_02.txt AC 6 ms 3800 KiB
sub1_03.txt AC 3 ms 3680 KiB
sub1_04.txt AC 10 ms 4236 KiB
sub1_05.txt AC 24 ms 4320 KiB
sub1_06.txt AC 24 ms 4196 KiB
sub1_07.txt AC 23 ms 4276 KiB
sub1_08.txt AC 24 ms 4244 KiB
sub1_09.txt AC 26 ms 4220 KiB
sub1_10.txt AC 24 ms 4328 KiB
sub1_11.txt AC 21 ms 4320 KiB
sub1_12.txt AC 26 ms 4256 KiB
sub1_13.txt AC 5 ms 3752 KiB
sub1_14.txt AC 14 ms 4304 KiB
sub1_15.txt AC 26 ms 4264 KiB
sub1_16.txt AC 26 ms 4200 KiB
sub1_17.txt AC 27 ms 4248 KiB
sub1_18.txt AC 29 ms 4320 KiB
sub1_19.txt AC 27 ms 4276 KiB
sub1_20.txt AC 30 ms 4244 KiB
sub1_21.txt AC 26 ms 4236 KiB
sub1_22.txt AC 25 ms 4316 KiB
sub1_23.txt AC 25 ms 4344 KiB
sub1_24.txt AC 35 ms 4404 KiB
sub1_25.txt AC 35 ms 4300 KiB
sub1_26.txt AC 35 ms 4324 KiB
sub1_27.txt AC 35 ms 4200 KiB
sub1_28.txt AC 3 ms 3672 KiB
sub1_29.txt AC 1 ms 3480 KiB
sub1_30.txt AC 7 ms 4196 KiB
sub1_small_01.txt AC 62 ms 3428 KiB
sub1_small_02.txt AC 62 ms 3452 KiB
sub1_small_03.txt AC 62 ms 3484 KiB
sub1_small_04.txt AC 62 ms 3456 KiB
sub1_small_05.txt AC 62 ms 3436 KiB
sub1_small_06.txt AC 62 ms 3540 KiB
sub1_small_07.txt AC 61 ms 3468 KiB
sub1_small_08.txt AC 61 ms 3460 KiB
sub1_small_09.txt AC 62 ms 3544 KiB
sub1_small_10.txt AC 62 ms 3540 KiB
sub1_small_11.txt AC 8 ms 3436 KiB
sub1_small_12.txt AC 2 ms 3544 KiB
sub1_small_13.txt AC 1 ms 3452 KiB
sub1_small_14.txt AC 1 ms 3536 KiB
sub1_small_15.txt AC 62 ms 3560 KiB
sub1_small_16.txt AC 62 ms 3436 KiB
sub1_small_17.txt AC 62 ms 3540 KiB
sub1_small_18.txt AC 62 ms 3432 KiB
sub1_small_19.txt AC 62 ms 3468 KiB
sub1_small_20.txt AC 61 ms 3624 KiB