Submission #851117

#	Time	Username	Problem	Language	Result	Execution time	Memory
851117		AliHasanli	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	37 ms	7504 KiB

molecules

#include<bits/stdc++.h>
using namespace std;
bool check(long long u,long long l,long long v)
{
    if(u>=v && v>=l)return 1;
    return 0;
}
vector<int>find_subset(int l,int u,vector<int> w)
{
    vector<int>empty;
    int n=w.size();
    vector<pair<long long,int>>v(n);
    for(int i=0;i<n;i++)
    {
        v[i].first=w[i];
        v[i].second=i;
    }
    sort(v.begin(),v.end());
    for(int i=1;i<n;i++)
    v[i].first+=v[i-1].first;
    int ll=0,r=0;
    vector<int>ans;
    while(ll<n)
    {
        if(ll==0)
        {
            if(check(u,l,v[r].first))
            {
                for(int i=0;i<=r;i++)
                {
                    ans.push_back(v[i].second);
                }
                return ans;
            }
            else if(u<v[r].first)
            {
                if(ll==r)
                {
                    if(r<n-1)
                    {
                        ll++;
                        r++;
                    }
                    else
                    {
                        return empty;
                    }
                }
                else
                {
                    if(ll<n-1)
                    ll++;
                    else return empty;
                }
            }
            else
            {
                if(r<n-1)
                r++;
                else return empty;
            }
        }
        else
        {
            if(check(u,l,v[r].first-v[ll-1].first))
            {
                for(int i=ll;i<=r;i++)
                {
                    ans.push_back(v[i].second);
                }
                return ans;
            }
            else if(u<v[r].first-v[ll-1].first)
            {
                if(ll==r)
                {
                    if(r<n-1)
                    {
                        ll++;
                        r++;
                    }
                    else return empty;
                }
                else
                {
                    if(ll<n-1)
                    ll++;
                    else return empty;
                }
            }
            else
            {
                if(r<n-1)
                r++;
                else return empty;
            }
        }
    }
    return empty;
}

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