Submission #986390

#	Time	Username	Problem	Language	Result	Execution time	Memory
986390		Pyqe	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	42 ms	7468 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fr first
#define sc second

long long n,z=0;
pair<long long,long long> a[200069];
queue<long long> q;
vector<int> sq;

vector<int> find_subset(int lh,int rh,vector<int> v)
{
    long long i,k,c;
    
    n=v.size();
    for(i=0;i<n;i++)
    {
    	a[i]={v[i],i};
	}
	sort(a,a+n,greater<pair<long long,long long>>());
	for(i=0;i<n&&z<lh;i++)
	{
		z+=a[i].fr;
		q.push(i);
	}
	if(z<lh)
	{
		return sq;
	}
	c=i;
	for(;z>rh;)
	{
		k=q.front();
		if(k>=c||k>=n-c)
		{
			return sq;
		}
		q.pop();
		z+=a[n-1-k].fr-a[k].fr;
		q.push(n-1-k);
	}
	for(;!q.empty();q.pop())
	{
		sq.push_back(a[q.front()].sc);
	}
	return sq;
}

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