Submission #422973

#TimeUsernameProblemLanguageResultExecution timeMemory
422973KienTranluvChaengDetecting Molecules (IOI16_molecules)C++17
19 / 100
1 ms288 KiB
#include <bits/stdc++.h>
//#include "molecules.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; sum = 0;
    for (int i = 0; i < n; ++ i){
        sum += v[i].w;
        if (sum > u){
            sum -= v[i].w;
            break;
        }
        q.push_back(i);
    }
    int rt = n - 1;
    while (sum < l && q.size() && rt > 0){
        sum -= v[q.front()].w;
        q.pop_front();
        sum += v[rt].w;
        q.push_back(rt);
        rt -= 1;
    }

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

    while (q.size()){
        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;
}*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...