Submission #722784

#	Time	Username	Problem	Language	Result	Execution time	Memory
722784		allin27x	Detecting Molecules (IOI16_molecules)	C++17	19 / 100	1 ms	340 KiB

molecules

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


vector<int> find_subset(int l, int u, vector<int> w){
	int n = w.size();
	int s1 = 0, s2 = 0;
	for (int sz = 1; sz<=n; sz++){
		s1 += w[sz-1]; s2+=w[n-sz];
		if (l<=s1 && s1<=u){
			vector<int> res(sz,0);
			for (int i=0; i<sz; i++) res[i] = i;
			return res;
		}
		if (l<=s2 && s2<=u){
			vector<int> res(sz,0);
			for (int i=0; i<sz; i++) res[i] = n-i-1;
			return res;
		}
		if (s1<l && s2>=l){
			vector<int> res(sz,0);
			for (int i=0; i<sz; i++) res[i] = i;
			for (int i=sz-1; i>=0; i--){
				if (s1-w[i]+w[n-sz+i]<l){
					s1+=w[n-sz+i]-w[i];
					res[i] = n-sz+i;
				} else {
					for (int j=i+1; s1<l; j++){
						s1+=w[j]-w[j-1];
						res[i] = j;
					}
					return res;
				}
			}
		}
	}
	return {};
}

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