Submission #422993

#	Time	Username	Problem	Language	Result	Execution time	Memory
422993		KienTranluvChaeng	Detecting Molecules (IOI16_molecules)	C++17	69 / 100	4 ms	588 KiB

molecules

#include <bits/stdc++.h>

using namespace std;

struct dou{
    int w, i;
};

bool how_sort(dou x, dou y){
    return x.w < y.w;
};

vector <int> find_subset(int l, int u, vector <int> w){
    int n = w.size();
    vector <dou> v(n);
    for (int i = 0; i < n; ++ i) v[i] = {w[i], i};

    vector <int> ans;
    deque <int> q;
    sort(v.begin(), v.end(), how_sort);
    int sum, id = -1; sum = 0;
    for (int i = 0; i < n; ++ i){
        sum += v[i].w;
        if (sum > u){
            sum -= v[i].w;
            id = i - 1;
            break;
        }
        q.push_back(i);
        if (i == n - 1) id = n - 1;
    }
    int rt = n - 1;
    while (sum < l && q.size() && rt > id){
        sum -= v[q.front()].w;
        q.pop_front();
        sum += v[rt].w;
        q.push_back(rt);
        rt -= 1;
    }

    if (sum > u || sum < l) return {};

    vector <int> dd(n);

    while (q.size()){
        if (dd[q.back()]){
            q.pop_back();
            continue;
        }
        dd[q.back()] = 1;
        ans.push_back(v[q.back()].i);
        q.pop_back();
    }
    return ans;
}

/*main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, l, u; cin >> n >> l >> u;
    vector <int> w(n);
    for (int i = 1; i <= n; ++ i) cin >> w[i - 1];
    auto v = find_subset(l, u, w);
    for (int i : v) cout << i << endl;
}*/

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