oj.uz

Submission #573147

# Submission time Handle Problem Language Result Execution time Memory
573147 2022-06-06T04:55:00 Z 1ne Bali Sculptures (APIO15_sculpture) C++14
0 / 100
 1 ms 320 KB 
#include<bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n,a,b;cin>>n>>a>>b;
	vector<int>arr(n);
	for (int i = 0;i<n;++i){
		cin>>arr[i];
	}
	sort(arr.begin(),arr.end());
	vector<multiset<long long>>bit(41);
	for (int i = 0;i<n;++i){
		for (long long j = 0;j<40;++j){
			if (arr[i] & (1LL<<j)){
				bit[j].insert(arr[i]);
			}
		}
	}
	long long ans = 0;
	for (int i = 0;i<40;++i){
		if ((int)bit[i].size()%2==1)ans|=(1LL<<i);
	}
	long long sz = n;
	while(sz > a){
		bool ok = false;
		for (long long i = 39;i>=0;--i){
			if ((int)bit[i].size() % 2 == 0 && (int)bit[i].size() > 1 &&sz - (int)bit[i].size() / 2 >=a){
				if (!bit[i + 1].empty()){
					auto it = bit[i].begin();
					auto it2 = prev(bit[i].end());
					vector<long long>val;
					while(*it2 > *it){
						auto temp = *it + *it2;
						for (long long j = 0;j<40;++j){
							if (temp & (1LL<<j)){
								bit[j].insert(temp);
							}
						}
						val.push_back(*it);
						val.push_back(*it2);
						++it;
						--it2;
					}
					sz-=(int)bit[i].size()/2;
					for (auto x:val){
						for (long long j = 0;j<40;++j){
							if (x & (1LL<<j)){
								bit[j].erase(bit[j].find(x));
							}
						}
					}
					ok = true;
					break;
				}
			}
			else if ((int)bit[i].size() % 2 == 1 && (int)bit[i].size() > 1){
				if (!bit[i + 1].empty()){
					auto it = bit[i].begin();
					auto it2 = prev(bit[i].end());
					vector<long long>val;
					while(it!=it2){
						auto temp = *it + *it2;
						for (long long j = 0;j<40;++j){
							if (temp & (1LL<<j)){
								bit[j].insert(temp);
							}
						}
						val.push_back(*it);
						val.push_back(*it2);
						++it;
						--it2;
						sz-=1;
						if (sz==a)break;
					}
					for (auto x:val){
						for (long long j = 0;j<40;++j){
							if ((1LL<<j)&x){
								bit[j].erase(bit[j].find(x));
							}
						}
					}
					ok = true;
					break;
				}
			}
		}
		//6 1 3
		//8 1 2 1 5 4
		if (!ok && sz > b){
			for (long long i = 0;i < 40;++i){
			if ((int)bit[i].size() % 2 == 0 && (int)bit[i].size() > 1 &&sz - (int)bit[i].size() / 2 >=a){
					auto it = bit[i].begin();
					auto it2 = prev(bit[i].end());
					vector<long long>val;
					while(*it2 > *it){
						auto temp = *it + *it2;
						for (long long j = 0;j<40;++j){
							if (temp & (1LL<<j)){
								bit[j].insert(temp);
							}
						}
						val.push_back(*it);
						val.push_back(*it2);
						++it;
						--it2;
					}
					sz-=(int)bit[i].size()/2;
					for (auto x:val){
						for (long long j = 0;j<40;++j){
							if (x & (1LL<<j)){
								bit[j].erase(bit[j].find(x));
							}
						}
					}
					ok = true;
					break;
				}
			else if ((int)bit[i].size() % 2 == 1 && (int)bit[i].size() > 1){
					auto it = bit[i].begin();
					auto it2 = prev(bit[i].end());
					vector<long long>val;
					while(it!=it2){
						auto temp = *it + *it2;
						for (long long j = 0;j<40;++j){
							if (temp & (1LL<<j)){
								bit[j].insert(temp);
							}
						}
						val.push_back(*it);
						val.push_back(*it2);
						++it;
						--it2;
						sz-=1;
						if (sz==a)break;
					}
					for (auto x:val){
						for (long long j = 0;j<40;++j){
							if ((1LL<<j)&x){
								bit[j].erase(bit[j].find(x));
							}
						}
					}
					ok = true;
					break;
				}
			}
		}
		if (!ok && sz > b){
			for (long long i = 0;i < 40;++i){
			if ((int)bit[i].size() % 2 == 0 && (int)bit[i].size() > 1){
					auto it = bit[i].begin();
					auto it2 = prev(bit[i].end());
					vector<long long>val;
					while(*it2 > *it){
						auto temp = *it + *it2;
						for (long long j = 0;j<40;++j){
							if (temp & (1LL<<j)){
								bit[j].insert(temp);
							}
						}
						val.push_back(*it);
						val.push_back(*it2);
						++it;
						--it2;
						sz-=1;
						if (sz<=b)break;
					}
					for (auto x:val){
						for (long long j = 0;j<40;++j){
							if (x & (1LL<<j)){
								bit[j].erase(bit[j].find(x));
							}
						}
					}
					ok = true;
					break;
				}
			}
		}
		else if (ok && sz > b){
			for (int i = 0;i<40;++i){
				if ((int)bit[i].size() % 2 == 1){
				auto it = bit[i].begin();
				for (long long j = 0;j<40;++j){
					if (j == i)continue;
					if (!bit[j].empty()){
						auto temp4  = prev(bit[j].end());
						auto temp2 = *temp4;
						if (temp2 == *it)continue;
						auto temp = temp2 + *it;
						auto temp3 = *it;
						for (long long k = 0;k<40;++k){
							if ((1LL<<k) & temp){
								bit[k].insert(temp);
							}
						}
						for (long long k = 0;k<40;++k){
							if ((1LL<<k) & temp2){
								bit[k].erase(bit[k].find(temp2));
							}
							if ((1LL<<k) & temp3){
								bit[k].erase(bit[k].find(temp3));
							}
						}
						ok = true;
						break;
					}
				}
				if (ok){
					sz--;
					break;
				}
			}
		}
		}
		else if (!ok)break;
	}
	for (long long i = 0;i<40;++i){
		if (!bit[i].empty())ans|=(1LL<<i);
	}
	cout<<ans<<'\n';
	return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 320 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Incorrect 1 ms 316 KB Output isn't correct
3 Halted 0 ms 0 KB -