Untitled
unknown
plain_text
4 years ago
3.8 kB
9
Indexable
#include <bits/stdc++.h>
using namespace std;
#define IOS \
ios::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define endl "\n"
#define Max(x, y, z) max(x, max(y, z))
#define Min(x, y, z) min(x, min(y, z))
#define fr(i, s, e) for (i = s; i < e; i++)
#define rf(i, s, e) for (i = s - 1; i >= e; i--)
#define pb push_back
#define eb emblace_back
#define mp make_pair
#define ff first
#define ss second
typedef long long ll;
typedef long double lld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vvvi> vvvvi;
typedef vector<long long> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<vvvll> vvvvll;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<vvc> vvvc;
typedef vector<pair<long long, long long>> vpll;
typedef vector<vector<pair<ll, ll>>> vvpll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
#define PI 3.141592653589793
#define MOD 1000000007
// typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update > pbds; // find_by_order, order_of_key
#ifndef ONLINE_JUDGE
#define debug(x) \
cerr << #x << " "; \
_print(x); \
cerr << endl;
#else
#define debug(x)
#endif
/*--------------------------------------------------------------------------------------------------------------------------*/
bool ok(ll checkThis, ll withThis, ll x, vector<bool> &selected, vector<ll> &arr)
{
if (!selected[checkThis])
{
if (((arr[checkThis] / withThis) >= x) || ((withThis / arr[checkThis]) >= x))
{
return true;
}
else
return false;
}
else
return false;
}
void solve()
{
ll n, x;
cin >> n >> x;
vector<ll> arr(n);
vector<bool> selected(n, 0);
for (ll i = 0; i < n; i++)
{
cin >> arr[i];
}
sort(arr.begin(), arr.end());
for (ll index = 0; index < n; index++)
{
if (!selected[index])
{
selected[index] = 1;
ll l = -1; //
ll r = n;
ll mid;
bool flag = false;
while (r > l + 1)
{
mid = l + (r - l) / 2;
// if(selected[mid])
// ++mid;
if (ok(mid, arr[index], x, selected, arr))
{
long double a = arr[index];
long double b = arr[mid];
// if (((arr[index] / arr[mid]) == x) || ((arr[mid] / arr[index]) == x))
// {
if (a >= b && ((a / b) - x < 1e-9))
{
flag = true;
selected[mid] = 1;
break;
}
else if (b >= a && ((b / a) - x < 1e-9))
{
flag = true;
selected[mid] = 1;
break;
}
else
r = mid;
}
else
{
l = mid;
}
}
if (flag)
continue;
else
selected[index] = 0;
}
}
ll counter = 0;
for (ll i = 0; i < n; i++)
{
if (selected[i] == 0)
++counter;
}
cout << counter << "\n";
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("Error.txt", "w", stderr);
#endif
IOS;
ll t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}Editor is loading...