2018 учебный год

(Na2a және теңдеу)

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

1 second

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

256 megabytes

Na2a информатика сабағында көп қылжағандықтан, мұғалім оған осы тапсырманы берді. Берілген $a_1,...,a_n,S$ сандары үшін, ($a_1 \oplus x) + (a_2 \oplus x) + ... + (a_n \oplus x) = S$ болатындай оң $x$ санын табу керек. Бұл жерде $\oplus$ операциясы биттік XOR немесе жоюшы НЕМЕСЕ. Бұл операция барлық заманауи бағдарламалау тілдерінде бар, С++ және 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
*/

C++

Copy