제출 #423008

#제출 시각아이디문제언어결과실행 시간메모리
423008KienTranluvChaengDetecting Molecules (IOI16_molecules)C++17
100 / 100
57 ms5572 KiB
#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 = w[i], v[i].i = i;

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

    if (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...