Submission #852936

#	Time	Username	Problem	Language	Result	Execution time	Memory
852936		waldi	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	40 ms	7280 KiB

molecules

#include <bits/stdc++.h>
#include "molecules.h"
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;

vector<int> find_subset(int l_int, int p_int, vector<int> a){
	ll l = l_int, p = p_int;
	int n = a.size();
	ll mini = a[0];
	for(ll x : a) mini = min(mini, x);
	
	vector<pli> b(n);
	REP(i, n) b[i] = {a[i]-mini, i};
	sort(b.begin(), b.end());
	
	ll lewo = 0ll, prawo = 0ll;
	FOR(ile, 1, n){
		lewo += b[ile-1].fi;
		prawo += b[n-ile].fi;
		
		if(max(l, lewo+mini*ile) <= min(p, prawo+mini*ile)){
			ll suma = lewo;
			REP(i, n){
				if(suma+mini*ile >= l){
					vector<int> ret;
					REP(off, ile) ret.emplace_back(b[i+off].se);
					return ret;
				}
				suma += b[i+ile].fi-b[i].fi;
			}
			printf("dupa\n");
			return {-1};
		}
	}
	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