Untitled
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...