Submission #333806

#	Time	Username	Problem	Language	Result	Execution time	Memory
333806		bigDuck	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	57 ms	6240 KiB

molecules

#include "molecules.h"
#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount



std::vector<int> find_subset(int l, int u, std::vector<int> w0) {
vector<int> res;

vector<pii> w;
int n=w0.size();
for(int i=0; i<n; i++){
    w.pb({w0[i], i});
}
sort(w.begin(), w.end());

int l1=0, r1=-1, l2=-1, r2=-1;
ll s=0;
for(int i=0; i<n; i++){
    if( (s+w[i].ft)>u ){ l1=0, r1=i-1; break;}
    s+=w[i].ft;
    if(  ( s>=l)  && (s<=u) ){
        for(int j=0; j<=i;j++){
            res.pb(w[j].sc);
        }
        return res;
    }
}
if( (r1==-1) ){return res;}


while( (s<l) && (  (l2>(r1+1) ) || (l2==-1) ) && (r1>=l1) ){
    if(r2==-1){
        s-=w[l1].ft; l1++; r2=n-1; l2=n-1; s+=w[l2].ft;
    }
    else{
        s-=w[l1].ft; l1++; l2--; s+=w[l2].ft;
    }
}

if(s<l){return res;}

for(int i=l1; i<=r1; i++){
    res.pb(w[i].sc);
}
for(int i=l2; (i<=r2) && (i>=0); i++){
    res.pb(w[i].sc);
}
return res;


}

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