제출 #722789

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
722789		allin27x	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	44 ms	7116 KiB

molecules

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

bool compare(pair<ll,ll> &a, pair<ll, ll> &b) {return a.first<b.first;}
vector<int> find_subset(int l, int u, vector<int> w){
	ll n = w.size();
	ll s1 = 0, s2 = 0;
	vector<pair<ll, ll>> t(n);
	for (int i=0; i<n; i++) t[i].first = w[i], t[i].second=i;
	sort(t.begin(), t.end());
	for (int sz = 1; sz<=n; sz++){
		s1 += t[sz-1].first; s2+=t[n-sz].first;
		if (l<=s1 && s1<=u){
			vector<int> res(sz,0);
			for (int i=0; i<sz; i++) res[i] = t[i].second;
			return res;
		}
		if (l<=s2 && s2<=u){
			vector<int> res(sz,0);
			for (int i=0; i<sz; i++) res[i] = t[n-i-1].second;
			return res;
		}
		if (s1<l && s2>u){
			vector<int> res(sz,0);
			for (int i=0; i<sz; i++) res[i] = t[i].second;
			for (int i=sz-1; i>=0; i--){
				if (s1-t[i].first+t[n-sz+i].first<l){
					s1+=t[n-sz+i].first-t[i].first;
					res[i] = t[n-sz+i].second;
				} else {
					for (int j=i+1; s1<l; j++){
						s1+=t[j].first-t[j-1].first;
						res[i] = t[j].second;
					}
					return res;
				}
			}
		}
	}
	return {};
}

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