제출 #863320

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
863320		20163070	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	35 ms	5716 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;
	}
};

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;
    long long 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: 31 / 31