Submission #549959

#	Time	Username	Problem	Language	Result	Execution time	Memory
549959		CyberSleeper	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	54 ms	5132 KiB

molecules

#include <bits/stdc++.h>
#include "molecules.h"
#define pii     pair<int, int>
#define fi      first
#define se      second
#define pb      push_back
#define ll      long long
using namespace std;

int N, r;
vector<pii> A;

vector<int> find_subset(int l, int u, vector<int> w) {
    r=u;
    vector<int> ans, MT;
    queue<pii> take;
    ll tot=0;
    N=w.size();
    for(int i=0; i<N; i++){
        A.pb({w[i], i});
        tot+=w[i];
    }
    if(tot<l)
        return MT;
    sort(A.begin(), A.end());
    if(r<A[0].fi)
        return MT;
    if(A[0].fi<=r && r<=A.back().fi){
        ans.pb(A[0].se);
        return ans;
    }
    if(A[0].fi<l && l<=A.back().fi){
        ans.pb(A.back().se);
        return ans;
    }
    tot=0;
    for(int i=0; i<N; i++){
        tot+=A[i].fi;
        take.push(A[i]);
        while(tot>r){
            tot-=take.front().fi;
            take.pop();
        }
        if(l<=tot && tot<=r){
            while(take.size()){
                ans.pb(take.front().se);
                take.pop();
            }
            return ans;
        }
    }
    return MT;
}

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