Solution #
If there’s only one element in the set, the graph is obvious bipartite. If there’s more than two elements, the graph will contains some cycles due to each pair of elements.
Suppose we have and in the set and the cycle will look like this:
It easy to see that the length of the cycle is which we want to be even. The length is even iff both and contains the same power of 2 in their factorizations. Otherwise and will have different parity, which means their sum is odd.(Try to prove by yourself)
Finally we need to find the largest subset whose elements have the same power of two and remove the rest elements.
Code #
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i <= int(r); ++i)
#define ford(i, n) for (int i = int(n)-1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
template<typename... Args>
void write(Args... args) { ((cout << args << " "), ...); cout<<endl;}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<ll> cnt[60];
forn(i,n){
ll x;
cin>>x;
ll tmp=x;
int c=0;
while(x%2==0) x/=2,c++;
cnt[c].pb(tmp);
}
int mx=0,idx;
forn(i,60) if(size(cnt[i])>mx){
mx=size(cnt[i]);
idx=i;
}
cout<<n-size(cnt[idx])<<endl;
forn(i,60){
if(i!=idx){
for(auto it:cnt[i]) cout<<it<<' ';
}
}
return 0;
}