Submission #910043

#	Time	Username	Problem	Language	Result	Execution time	Memory
910043		pragmatist	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	39 ms	5460 KiB

molecules

#include <bits/stdc++.h>

using namespace std;

const int N = (int)2e5 + 7;

int n;
pair<int, int> a[N];
int L, R;

vector<int> find_subset(int _l, int _u, vector<int> _w) {
    n = (int)_w.size();
    L = _l;
    R = _u;
    for(int i = 0; i < n; ++i) {
        a[i+1] = {_w[i], i};
    }
    sort(a+1, a+1+n);
    if(a[1].first >= L && a[1].first <= R) {
        return {a[1].second};
    }
    if(a[n].first >= L && a[n].first <= R) {
        return {a[n].second};
    }
    if(R < a[1].first) {
        return {};
    }
    int j = 1;
    long long cur = 0;
    for(int i = 1; i <= n; ++i) {
        cur += a[i].first;
        while(j<i && cur-a[j].first >= L) {
            cur -= a[j++].first;
        }
        if(cur >= L && cur <= R) {
            vector<int> ans;
            for(int k = j; k <= i; ++k) {
                ans.push_back(a[k].second);
            }
            return ans;
        }
    }
    return {};
}

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