Submission #219649

#	Time	Username	Problem	Language	Result	Execution time	Memory
219649		summitwei	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	75 ms	8772 KiB

molecules

#include <bits/stdc++.h>
#include <molecules.h>
using namespace std;
typedef vector<int> vi;
typedef vector<pair<int, int> > vpii;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef vector<ll> vll;
#define INF 1000000000000000000LL
#define MOD 1000000007LL
#define EPSILON 0.00001
#define f first
#define s second
#define pb push_back
#define mp make_pair

#define FOR(i, a, b) for (int i=(a); i<=(signed)(b); i++)
#define F0R(i, a) for (int i=0; i<(signed)(a); i++)
#define RFOR(i, a, b) for (int i=(a); i >= b; i--)

#define MN 200005
pll a[MN];
ll ps[MN];
vi find_subset(int l, int u, vi w){
    int n = w.size();
    F0R(i, n) a[i+1] = {w[i], i};
    sort(a+1, a+n+1);
    FOR(i, 1, n) ps[i] = ps[i-1]+a[i].f;
    //F0R(i, n+1) cout << ps[i] << " ";
    //cout << "\n";
    FOR(lb, 0, n){
        int rb = lower_bound(ps, ps+n+1, l+ps[lb])-ps;
        if(rb <= n && ps[rb]-ps[lb] <= u){
            vi ans;
            FOR(i, lb+1, rb){
                ans.pb(a[i].s);
            }
            return ans;
        }
    }
    vi ans;
    return ans;
}

/*int main(){
    //ios_base::sync_with_stdio(false);
    //cin.tie(0);

    int n, l, u;
    cin >> n >> l >> u;
    vi w(n);
    F0R(i, n) cin >> w[i];
    
    vi res = find_subset(l, u, w);
    for(auto u : res) cout << u << " ";
    cout << "\n";
    
    return 0;
}*/

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 23 / 23
• Subtask 6: 31 / 31