Code : GCD is Greater
#include <bits/stdc++.h>
using namespace std;
// If you remove elements from a set, gcd would increase or remain same.
// If you add elements to a set, the bitwise AND would decrease or remain same.
// gcd > 'and' + x
// Therefore, it's always optimal to make the size of gcd set as small as
// possible and the size of 'and' set as large as possible.
// Therefore, we will have 2 elements on LHS and n - 2 elements in RHS.
// Now, we just need to find the pair that satisfies this equation.
#define endl "\n"
void solve(vector<int> &a, int x) {
int n = a.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int g = __gcd(a[i], a[j]);
// ~ flips all the bits
int b = ~0;
vector<int> blue;
for (int k = 0; k < n; k++) {
if (k == i || k == j) {
continue;
}
blue.push_back(a[k]);
b &= a[k];
}
if (g > b + x) {
cout << "YES" << endl;
cout << 2 << " ";
cout << a[i] << " " << a[j] << endl;
cout << n - 2 << " ";
for (auto &ele : blue) {
cout << ele << " ";
}
cout << endl;
return;
}
}
}
cout << "NO" << endl;
}
int main() {
int t;
cin >> t;
for (int zz = 0; zz < t; zz++) {
int n, x;
cin >> n >> x;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
solve(a, x);
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
// If you remove elements from a set, gcd would increase or remain same.
// If you add elements to a set, the bitwise AND would decrease or remain same.
// gcd > 'and' + x
// Therefore, it's always optimal to make the size of gcd set as small as
// possible and the size of 'and' set as large as possible.
// Therefore, we will have 2 elements on LHS and n - 2 elements in RHS.
// Now, we just need to find the pair that satisfies this equation.
#define endl "\n"
const int mb = 20;
void solve(vector<int> &a, int x) {
int n = a.size();
vector<int> zero_cnt(mb);
for (int i = 0; i < n; i++) {
for (int bit = 0; bit < mb; bit++) {
if (!((1 << bit) & a[i])) {
zero_cnt[bit]++;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int g = __gcd(a[i], a[j]);
int b = 0;
for (int bit = 0; bit < mb; bit++) {
int have = zero_cnt[bit];
if (!((1 << bit) & a[i])) {
have--;
}
if (!((1 << bit) & a[j])) {
have--;
}
if (!have) {
b |= (1 << bit);
}
}
if (g > b + x) {
cout << "YES" << endl;
cout << 2 << " ";
cout << a[i] << " " << a[j] << endl;
cout << n - 2 << " ";
for (int k = 0; k < n; k++) {
if (k == i || k == j) {
continue;
}
cout << a[k] << " ";
}
cout << endl;
return;
}
}
}
cout << "NO" << endl;
}
int main() {
int t;
cin >> t;
for (int zz = 0; zz < t; zz++) {
int n, x;
cin >> n >> x;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
solve(a, x);
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
// If you remove elements from a set, gcd would increase or remain same.
// If you add elements to a set, the bitwise AND would decrease or remain same.
// gcd > 'and' + x
// Therefore, it's always optimal to make the size of gcd set as small as
// possible and the size of 'and' set as large as possible.
// Therefore, we will have 2 elements on LHS and n - 2 elements in RHS.
// Now, we just need to find the pair that satisfies this equation.
#define endl "\n"
const int mb = 20;
void solve(vector<int> &a, int x) {
int n = a.size();
vector<int> zero_cnt(mb);
vector<vector<int>> zero_pos(mb, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
for (int bit = 0; bit < mb; bit++) {
if (!((1 << bit) & a[i])) {
zero_cnt[bit]++;
zero_pos[bit].push_back(i);
}
}
}
auto check = [&](int i, int j) -> bool {
int g = __gcd(a[i], a[j]);
int b = 0;
for (int bit = 0; bit < mb; bit++) {
int have = zero_cnt[bit];
if (!((1 << bit) & a[i])) {
have--;
}
if (!((1 << bit) & a[j])) {
have--;
}
if (!have) {
b |= (1 << bit);
}
}
if (g > b + x) {
cout << "YES" << endl;
cout << 2 << " ";
cout << a[i] << " " << a[j] << endl;
cout << n - 2 << " ";
for (int k = 0; k < n; k++) {
if (k == i || k == j) {
continue;
}
cout << a[k] << " ";
}
cout << endl;
return true;
}
return false;
};
for (int bit = 0; bit < mb; bit++) {
if (zero_cnt[bit] == 0 || zero_cnt[bit] > 2) {
continue;
}
auto &vec = zero_pos[bit];
for (int idx = 0; idx < (int)vec.size(); idx++) {
int i = vec[idx];
for (int j = 0; j < n; j++) {
if (i == j) {
continue;
}
if (check(i, j)) {
return;
}
}
}
}
// If we haven't found an answer so far, the bitwise AND of any feasible
// subset is fixed.
// We just need to find if we can make
// gcd > fixed_bitwise_and + x.
// This is just equal to finding the max gcd and verifying it as the
// candidate.
int mx = *max_element(a.begin(), a.end());
vector<vector<int>> pos(mx + 1);
for (int i = 0; i < n; i++) {
pos[a[i]].push_back(i);
}
for (int g = mx; g >= 1; g--) {
vector<int> have;
for (int m = g; m <= mx; m += g) {
for (auto &ele : pos[m]) {
have.push_back(ele);
if (have.size() >= 2) {
break;
}
}
}
if (have.size() < 2) {
continue;
}
if (check(have[0], have[1])) {
return;
}
}
cout << "NO" << endl;
}
int main() {
int t;
cin >> t;
for (int zz = 0; zz < t; zz++) {
int n, x;
cin >> n >> x;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
solve(a, x);
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
// If you remove elements from a set, gcd would increase or remain same.
// If you add elements to a set, the bitwise AND would decrease or remain same.
// gcd > 'and' + x
// Therefore, it's always optimal to make the size of gcd set as small as
// possible and the size of 'and' set as large as possible.
// Therefore, we will have 2 elements on LHS and n - 2 elements in RHS.
// Now, we just need to find the pair that satisfies this equation.
#define endl "\n"
const int mb = 20;
void solve(vector<int> &a, int x) {
int n = a.size();
vector<int> zero_cnt(mb);
vector<vector<int>> zero_pos(mb, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
for (int bit = 0; bit < mb; bit++) {
if (!((1 << bit) & a[i])) {
zero_cnt[bit]++;
zero_pos[bit].push_back(i);
}
}
}
auto check = [&](int i, int j) -> bool {
int g = __gcd(a[i], a[j]);
int b = 0;
for (int bit = 0; bit < mb; bit++) {
int have = zero_cnt[bit];
if (!((1 << bit) & a[i])) {
have--;
}
if (!((1 << bit) & a[j])) {
have--;
}
if (!have) {
b |= (1 << bit);
}
}
if (g > b + x) {
cout << "YES" << endl;
cout << 2 << " ";
cout << a[i] << " " << a[j] << endl;
cout << n - 2 << " ";
for (int k = 0; k < n; k++) {
if (k == i || k == j) {
continue;
}
cout << a[k] << " ";
}
cout << endl;
return true;
}
return false;
};
vector<int> in_blue_set(n, false);
for (int bit = 0; bit < mb; bit++) {
if (zero_cnt[bit] == 0 || zero_cnt[bit] > 2) {
continue;
}
auto &vec = zero_pos[bit];
for (int idx = 0; idx < (int)vec.size(); idx++) {
int i = vec[idx];
for (int j = 0; j < n; j++) {
if (i == j) {
continue;
}
if (check(i, j)) {
return;
}
}
}
// If an answer wasn't found, these numbers need to be locked inside
// the blue set, so that other numbers can be chosen freely while
// calculating gcd.
for (auto &i : vec) {
in_blue_set[i] = true;
}
}
// If we haven't found an answer so far, the bitwise AND of any feasible
// subset is fixed.
// We just need to find if we can make
// gcd > fixed_bitwise_and + x.
// This is just equal to finding the max gcd and verifying it as the
// candidate.
int mx = *max_element(a.begin(), a.end());
vector<vector<int>> pos(mx + 1);
for (int i = 0; i < n; i++) {
pos[a[i]].push_back(i);
}
for (int g = mx; g >= 1; g--) {
vector<int> have;
for (int m = g; m <= mx; m += g) {
if (have.size() >= 2) {
break;
}
for (auto &idx : pos[m]) {
if (in_blue_set[idx]) {
continue;
}
have.push_back(idx);
if (have.size() >= 2) {
break;
}
}
}
// We found a gcd that is a multiple of g.
// This must be the largest gcd. If this doesn't work, none
// of the others would.
if (have.size() >= 2 && check(have[0], have[1])) {
return;
}
}
cout << "NO" << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
for (int zz = 0; zz < t; zz++) {
int n, x;
cin >> n >> x;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
solve(a, x);
}
return 0;
}