---
tags: IOI
---
# IOI2016 Day1-1 分子の検出 (Detecting Molecules)

簡単か？

## 問題文

https://www.ioi-jp.org/ioi/2016/tasks/day1-molecules-JPN.pdf
https://oj.uz/problem/view/IOI16_molecules

数列 $w$ と区間 $[l, u]$ が与えられます。
ただし $u - l ≥ max(w) - min(w)$ です。
空でない $w$ の(連続のほうでない)部分列であって合計が $[l, u]$ に入っているものを1つ求めてください。

## 考察

$u - l ≥ max(w) - min(w)$ がかなり重要そう。
これの意味を考えると、合計が $u$ を超えた部分列の選ぶものを小さいものに変更しても $[l, u]$ を通り過ぎることはないことがわかる。
そこで、大きい方から選んで行って、合計が $u$ を超えたら選ぶものを小さいものに変えていけばよい。

## 実装

https://oj.uz/submission/210848

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#include "molecules.h"
#define rep(a) for(ll i = 0; i < a; i++)
#define all(a) begin(a), end(a)
#define sum(a) accumulate(all(a), 0LL)
 
vector<int> find_subset(int l, int u, vector<int> w){
    ll n = w.size();
    vector<ll> a(n);
    iota(all(a), 0);
    sort(all(a), [&](ll a, ll b){ return w[a] < w[b]; });
    if(w[a[0]] > u) return {};
    if(l > sum(w)) return {};
    ll s = 0, at = n;
    vector<int> ans;
    while(s <= u){
        if(l <= s) return ans;
        ans.push_back(a[--at]);
        s += w[ans.back()];
    }
    n = min<ll>(ans.size(), n - ans.size());
    rep(n){
        s -= w[ans[i]];
        ans[i] = a[i];
        s += w[ans[i]];
        if(s <= u) return ans;
    }
    return {};
}