Submission #852936

#TimeUsernameProblemLanguageResultExecution timeMemory
852936waldiDetecting Molecules (IOI16_molecules)C++17
100 / 100
40 ms7280 KiB
#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 {};
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...