Submission #863313

#	Time	Username	Problem	Language	Result	Execution time	Memory
863313		20163070	Detecting Molecules (IOI16_molecules)	C++14	69 / 100	27 ms	5464 KiB

molecules

#include <bits/stdc++.h>
#include "molecules.h"
using namespace std;

struct node
{
	int id,mark;
	bool operator < (const node &b)const
	{
		return mark<b.mark;
	}
};

bool cmp(node a,node b)
{
	return a.mark<b.mark;
}

std::vector<int> find_subset(int ll, int rr, std::vector<int> w) {
	int n=w.size();
    vector<node> p(n);
    for(int i=0;i<n;i++)
    {
    	p[i].id=i;
    	p[i].mark=w[i];
	}
	sort(p.begin(),p.end());
	int l=0,r=0;
    int res=p[0].mark;
    vector<bool> st(n+1,0);
    st[0]=1;
    while(l<=r&&l<n&&r<n)
    {
    	if(res<ll) res+=p[++r].mark,st[r]=1;
    	else if(res>rr) res-=p[l++].mark,st[l-1]=0;
    	else
    	{
    		vector<int> t;
    		for(int i=0;i<n;i++)
    		{
    			if(st[i]) t.push_back(p[i].id);
			}
    		return t;
		}
	}
	vector<int> tt;
	return tt;
}

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