Cod sursa(job #2674149)

Utilizator mex7Alexandru Valentin mex7 Data 18 noiembrie 2020 18:09:51
Problema Arbore partial de cost minim Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int t;

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

    cin >> t;
    for (int q = 1; q <= t; q++) {
        ll n, w, x;
        vector <ll> v;
        map <ll, queue <int> > pos;

        cin >> n >> w;
        for (int i = 1; i <= n; i++) {
            cin >> x;
            v.push_back(x);
            pos[x].push(i);
        }

        sort(v.begin(), v.end());

        vector <int> result;
        bool found = false;
        ll sum = 0;
        for (int i = 0; i < n && !found; i++) {
            vector <ll> :: iterator num = lower_bound(v.begin() + i, v.end(), (w + 1) / 2 - sum);
            if (num != v.end() && *num + sum <= w) {
                result.push_back(pos[*num].front());
                pos[*num].pop();
                found = true;
                break;
            }
            sum += v[i];
            result.push_back(pos[v[i]].front());
            pos[v[i]].pop();
            if (sum >= (w + 1) / 2 && sum <= w)
                found = true;
        }

        if (found) {
            cout << result.size() << '\n';
            for (int i : result)
                cout << i << ' ';
        } else
            cout << -1;

        cout << '\n';
    }

    return 0;
}