Untitled

 avatar
unknown
plain_text
3 years ago
3.8 kB
6
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...