- Quiz
- AC
- 解説
- 各荷物1つで条件を満たすかチェックする
- 満たさなかった場合、荷物の重さは floor(W/2)より小さいか、Wより大きいものしかない
- floor(W/2)より小さい荷物を貪欲に足していってもWを突然超えることはないので、貪欲に足していって条件を満たすか確認すればよい
- ポイント
- 各要素を単体チェックすることで、入力の値域を絞れる
void solve(){
ll N,C;
cin>>N>>C;
debug(N,C);
ll left = (C+1)/2;
VI A(N);
rep(i, N){
cin >> A[i];
}
if(MIN(A)>C){
p(-1);return;
}
{
ll sum = SUM(A);
if(sum<left){
p(-1);return;
}
}
rep(i,N){
ll w = A[i];
if(left<=w && w<=C){
p(1);
p(i+1);
return;
}
}
VI Ans;
ll sum=0;
rep(i,N){
if(A[i]>C)continue;
sum += A[i];
Ans.push_back(i);
if(left<=sum && sum<=C){
p(SZ(Ans));
print_vector(Ans);
return;
}
}
p(-1);
}
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
ll N;
cin>>N;
while(N--)solve();
return 0;
}