Submission #576696

#	Time	Username	Problem	Language	Result	Execution time	Memory
576696		Halym2007	Detecting Molecules (IOI16_molecules)	C++11	100 / 100	50 ms	8860 KiB

molecules

#include <bits/stdc++.h>
#define ff first
#define ss second
#define cont continue;
#define sz size()
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 300005;
// a1 a2 tapmaly
ll n, ans, p[N], a1, a2, l1, r1, md, hp, slm;
vector <int> q;
vector <pair <ll, ll> > v;
vector <int> find_subset(int l, int u, vector <int> w) {
	n = w.sz;
	a1 = 2*n;
	for (int i = 0; i < n; ++i) {
		v.pb ({w[i], i});
	}
	sort (v.begin (), v.end());
	p[0] = v[0].ff;
	for (int i = 1; i < n; ++i) {
		p[i] = p[i - 1] + v[i].ff;
	}
	for (int i = 0; i < n; ++i) {
		l1 = i;
		r1 = n-1;
		while (l1 <= r1) {
			md = (l1 + r1) / 2;
			if (!i) hp = p[md];
			else hp = p[md] - p[i - 1];
			if (hp > u) r1 = md - 1;
			else if (hp < l) l1 = md + 1;
			else{
				a1 = i;
				a2 = md;
				slm = 1;
				break;
			}
		}
		if (slm) break;
	}
	for (int i = a1; i <= a2; ++i) q.pb (v[i].ss);
	sort(q.begin(), q.end());
	return q;
}
/*
 int main () {
 	vector <int> a = {6, 8, 8, 7};
 	for (int i = 0; i < find_subset(15, 17, a).size(); i++){
 		cout << find_subset(15, 17, a)[i] << " ";
 	}
 }
 */

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