Submission #208652

#	Time	Username	Problem	Language	Result	Execution time	Memory
208652		DavidDamian	Detecting Molecules (IOI16_molecules)	C++11	100 / 100	73 ms	4204 KiB

molecules

#include "molecules.h"
#include<bits/stdc++.h>
using namespace std;
///Sliding Window
///Determine a subset of numbers with sum between L and R
typedef long long ll;
struct number
{
    int x;
    int id;
};
bool byNumber(number a,number b)
{
    return a.x<b.x;
}
vector<number> A;
vector<int> find_subset(int l, int r, vector<int> w) {
    int n=w.size();
    for(int i=0;i<n;i++){
        number x={w[i],i};
        A.push_back(x);
    }
    sort(A.begin(),A.end(),byNumber);
    int a=0,b=-1;
    ll sum=0;
    while(b<n){
        if(l<=sum && sum<=r) break;
        if(sum<l){
            b++;
            if(b<n) sum+=(ll)A[b].x;
        }
        else{
            sum-=(ll)A[a].x;
            a++;
        }
    }
    vector<int> ans;
    if(l<=sum && sum<=r){
        for(int i=a;i<=b;i++){
            ans.push_back(A[i].id);
        }
    }
    return ans;
}

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