Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ∧_∧
- ( ・ω・。)つ━☆・*。
- ⊂ ノ ・゜
- しーJ Accepted
- */
- // #pragma GCC optimize("O3")
- // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- #define ll long long
- #define all(x) begin(x), end(x)
- #define x first
- #define y second
- #define int long long
- using namespace std;
- using namespace __gnu_pbds;
- typedef long double ld;
- template<typename T>
- using kawaii_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
- const ld PI = atan2(0, -1);
- void seriy() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cout << fixed << setprecision(14);
- #ifdef _offline
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- }
- const int MAXN = 3e5 + 100;
- const int MAXM = 600;
- const int INF = 1e18 + 7;
- const int BASE = 47;
- const int MOD = 1e9 + 7;
- const int MAXLOG = 51;
- const ld EPS = 1e-6;
- vector<int> a_int;
- vector<string> a;
- int n;
- string b;
- int b_int, ans_int = -1;
- int dec(string s) {
- int sum = 0;
- for(int i = 0; i < s.size(); i++) {
- if(s[i] == '1') {
- sum += (1ll << i);
- }
- }
- return sum;
- }
- string bin(int a) {
- string t = "";
- bool f = 0;
- for(int i = MAXLOG; i >= 0; i--) {
- if(a >= (1ll << i)) {
- f = 1;
- t += '1';
- a -= (1ll << i);
- }
- else if(f) {
- t += '0';
- }
- }
- if(t.size() == 0) t = "0";
- return t;
- }
- void add(string &s, int pw) {
- int p = pw;
- while(s.size() - 1 < p) {
- s += '0';
- }
- while(p < s.size() && s[p] == '1') {
- s[p] = '0';
- p++;
- }
- // cerr << s << " " << p << '\n';
- if(p < s.size()) {
- s[p] = '1';
- }
- else {
- s += '1';
- }
- }
- void subtract(string &s, int pw) {
- int p = pw;
- while(p < s.size() && s[p] == '0') {
- s[p] = '1';
- p++;
- }
- s[p] = '0';
- }
- string xor1(string &a, string &b) {
- string ans;
- ans.resize(max(a.size(), b.size()), '0');
- for(int i = 0; i < max(a.size(), b.size()); i++) {
- if(i < min(a.size(), b.size())) {
- }
- else if(a.size() < b.size()) {
- a += '0';
- }
- else if(a.size() > b.size()){
- b += '0';
- }
- ans[i] = ((a[i] == b[i]) ? '0' : '1');
- }
- return ans;
- }
- string ans = "-1";
- void solve(string cur, int pw, string cur_sum) {
- if(pw > b.size()) {
- string kek = cur_sum;
- while(kek.back() == '0') {
- kek.pop_back();
- }
- if(!kek.size()) {
- kek = "0";
- }
- if(kek == b) {
- ans = cur;
- }
- return;
- }
- cerr << cur << " " << cur_sum << '\n';
- if(cur_sum[pw] == b[pw]) {
- solve(cur, pw + 1, cur_sum);
- }
- if(ans != "-1") {
- return;
- }
- string sum = "0";
- for(int i = 0; i < n; i++) {
- add(a[i], pw);
- sum = xor1(sum, a[i]);
- }
- string sum_c = sum;
- while(sum_c.back() == '0') {
- sum_c.pop_back();
- }
- // cerr << sum << " " << pw << '\n';
- if(sum_c[pw] == b[pw]) {
- cur[pw] = '1';
- solve(cur, pw + 1, sum);
- }
- for(int i = 0; i < n; i++) {
- subtract(a[i], pw);
- }
- }
- void solve2(int cur, int pw, int cur_sum) {
- if(pw > b.size()) {
- if(cur_sum == b_int) {
- ans_int = cur;
- }
- return;
- }
- cerr << cur << " " << cur_sum << " " << bin(cur) << " " << bin(cur_sum) << '\n';
- if(((cur_sum >> pw) & 1) == ((b_int >> pw) & 1)) {
- solve2(cur, pw + 1, cur_sum);
- }
- if(ans_int != -1) {
- return;
- }
- int sum = 0;
- for(int i = 0; i < n; i++) {
- a_int[i] += (1ll << pw);
- sum ^= a_int[i];
- }
- if(((sum >> pw) & 1) == ((b_int >> pw) & 1)) {
- cur += (1ll << pw);
- solve2(cur, pw + 1, sum);
- }
- for(int i = 0; i < n; i++) {
- a_int[i] -= (1ll << pw);
- }
- }
- signed main() {
- seriy();
- cin >> n;
- a.resize(n);
- a_int.resize(n);
- int cur_sum_int = 0;
- string cur_sum = "0";
- for(int i = 0; i < n; i++) {
- string h;
- cin >> h;
- a[i] = h;
- reverse(all(a[i]));
- a_int[i] = dec(a[i]);
- cur_sum_int ^= a_int[i];
- cur_sum = xor1(cur_sum, a[i]);
- }
- string bb;
- cin >> bb;
- b = bb;
- reverse(all(b));
- b_int = dec(b);
- string s;
- s.resize(b.size(), '0');
- solve(s, 0, cur_sum);
- cerr << '\n';
- solve2(0, 0, cur_sum_int);
- while(ans.back() == '0') {
- ans.pop_back();
- }
- reverse(all(ans));
- if(ans == "1-") ans = "-1";
- if(!ans.size()) ans = "0";
- // cout << ((ans_int == -1) ? "-1" : bin(ans_int)) << '\n';
- cout << ans;
- // cout << ((ans == "-1") ? "-1" : ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement