Республиканская олимпиада по информатике. 2018 год

Задача E. Na2a и уравнение

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Na2a много баловался на уроке информатики, и учитель в наказание ему придумал следующую задачу. Найти неотрицательное целое число $x$, такое что ($a_1 \oplus x) + (a_2 \oplus x) + ... + (a_n \oplus x) = S$, где $a_1,...,a_n,S$ — заданные числа. Здесь $\oplus$ обозначает операцию побитового XOR или исключающего ИЛИ. Данная операция существует во всех современных языках программирования, например, в языках C++ и Java она обозначена как <<$\string^$>>, в Pascal — как <>. Помогите Na2a решить данное уравнение.

Формат входного файла

В первой строке находятся два целых числа $n$, $S (1 \le n \le 10^5, 0 \le S \le 10^{12})$. Во второй строке находятся $n$ целых числа $a_1$, $a_2$, ..., $a_n(0 \le a_i \le 10^{12})$.

Формат выходного файла

Выведите -$1$, если уравнение не имеет неотрицательных решений. Иначе выведите такое $x(x \ge 0)$, что описанное в условии равенство выполняется. Если существует несколько ответов, выведите любой из них.

Система оценки

Данная задача содержит пять подзадач, в каждой подзадаче выполняются ограничения из условии и:

1. $n \le 1000, a_i,s \le 1000$. Оценивается в $7$ баллов.
2. $n = 2, a_i,s \le 10^{12}$. Оценивается в $22$ баллов.
3. $n \le 10^4, a_i,s \le 10^6$. Оценивается в $20$ баллов.
4. $n \le 10^5, a_i,s \le 5 \cdot 10^7$. Оценивается в $16$ баллов.
5. $n \le 10^5, a_i,s \le 10^{12}$. Оценивается в $35$ баллов.

Пример:

Вход

3 4
1 2 3

Ответ

2

\Note Таблица для исключающего ИЛИ.\\ 1 $xor$ 1 = 1, 1 $xor$ 0 = 1\\ 0 $xor$ 1 = 1, 0 $xor$ 0 = 0\\ Например, если $X$ = $109_{10}$ = $1101101_{2}$, $Y$ = $41_{10}$ = $101001_{2}$ тогда: $X$ $\oplus$ $Y$ = $68_{10}$ = $1000100_{2}$. ( Temirlan Satylkhanov )

Комментарий/решение

1 xor 1 = 0

показать/скрыть код

#include <bits/stdc++.h>
#define N 55
#define pb push_back
#define fi first
#define se second
#define si size()
#define ll unsigned long long
#define mp make_pair
#define iter ::iterator
#define all(v) v.begin(), v.end()
#define pp pop_back
#define mapiter map<int, int>::iterator
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forn1(i, n) for(int i = 1; i <= n; ++i)
#define forr(i, n)	for(int i = n - 1; i >= 0; --i)
#define forr1(i, n)	for(int i = n; i >= 1; --i)
#define form(l, r, i)	for(int i = l; i <= r; ++i)
#define forv(r, l, i)	for(int i = r; i >= l; --i)
#define r0 return 0
#define barnarnar ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lld long double
#define elif else if
 
const int inf = 1e9 + 7;
const lld EPS = 0.00000001;
const ll modw = 1e9 + 7;
 
using namespace std;

ll bits[N];
ll a[N];
ll s1[N], s2[N];
bool fl = 0;
ll n, need;
int lst;

void get(ll a)
{
	for(int i = 0; i <= 50; i++)
	{
		if(1 & (a >> i))
		{
			bits[i]++;
		}
	}
}

void rec(ll sum, bool used[N], int pos)
{
	if(fl)	return;
	if(pos == lst + 1)
	{
		//cout << "SUM: " << sum << endl;
		if(sum == need)
		{
			ll ans = 0;
			//cout << sum << endl;
			for(int i = 0; i <= 50; i++)
			{
				//cout << used[i];
				if(used[i])	ans += (1 << i);
			}
			//cout << endl;
			cout << ans;
			fl = 1;
		}
		return;
	}
	used[pos] = 0;
	sum += s1[pos];
	rec(sum, used, pos + 1);
	used[pos] = 1;
	sum -= s1[pos];
	sum += s2[pos];
	rec(sum, used, pos + 1);
}

int main()
{
	barnarnar
	cin >> n >> need;
	forn(i, n)
	{
		cin >> a[i];
		get(a[i]);
	}
	//forn(i, 50)	cout << bits[i] << ' ';
	bool used[N];
	forn(i, N)	used[i] = 0;
	forr(i, N)
	{
		if(bits[i] >= 1)
		{
			lst = i;
			break;
		}
	}
	for(int i = 0; i <= lst; i++)
	{
		s1[i] = (1 << i) * bits[i];
		s2[i] = (1 << i) * (n - bits[i]);
		//cout << s1[i] << ' ' << s2[i] << endl;
	}
	rec(0, used, 0);
	if(!fl)	cout << -1;
	return 0;
}
/*
4 31
1 2 3 9
*/