Submission #67164164

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    while(T--) {
        int n; cin >> n;
        vector<int> v(n);
        for(int i = 0; i < n; i++) cin >> v[i];

        if(n > 2) sort(v.begin() + 1, v.end() - 1);

        int start = 0, end = n - 1;
        int ans = 1;

        if(n == 2) {
            if(v[0] * 2 >= v[1]) cout << 2 << "\n";
            else cout << -1 << "\n";
            continue;
        }

        while(true) {
            if(start == n - 2) {
                if(v[start] * 2 >= v[n-1]) cout << ans + 1 << "\n";
                else cout << -1 << "\n";
                break;
            }

            if(v[start] * 2 >= v[end]) {
                cout << ans + 1 << "\n";
                break;
            }

            int willTopple = upper_bound(v.begin() + start + 1, v.end() - 1, 2 * v[start]) - v.begin() - 1;

            if(willTopple <= start) {
                cout << -1 << "\n";
                break;
            }

            if(v[start] != v[willTopple]) ans++;
            start = willTopple;
        }
    }
    return 0;
}

Submission Info

Judge Result