Submission #1354604

#TimeUsernameProblemLanguageResultExecution timeMemory
1354604gvancakDetecting Molecules (IOI16_molecules)C++20
100 / 100
27 ms6168 KiB
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long
using namespace std;
//#include "molecules.h"

vector<int> find_subset(int L, int R, vector<int> w) {
	
	vector <pair <long long,long long> > v;
	vector <int> ans;
	ans.clear();
	v.clear();
	for (int i=0; i<w.size(); i++) v.pb(mp(w[i],i));
	sort(v.begin(),v.end());
	if (v[0].f>R) return {};
	
	int l=0; int r=v.size();
	long long sum=0;
	for (int i=0; i<v.size(); i++){
		sum+=v[i].f;
		if (sum>=L){
			r=i; break;
		}
	}
	
	if (sum<L) return {};
	if (sum<=R){
		for (int i=0; i<=r; i++) ans.pb(v[i].s);
		return ans;
	}
	sum-=v[r].f;
	r--;
	int st=r;
	for (int i=st; i<v.size(); i++){
		if (sum>=L && sum<=R) break;
		sum-=v[l].f; l++; r++; sum+=v[r].f; 
	}
	//cout<<sum<<endl;
	if (sum<L || sum>R) return ans;
	for (int i=l; i<=r; i++){
		ans.pb(v[i].s);
	}
	return ans;
	
}
/*
int main() {
    int n, l, u;
    assert(3 == scanf("%d %d %d", &n, &l, &u));
    std::vector<int> w(n);
    for (int i = 0; i < n; i++)
        assert(1 == scanf("%d", &w[i]));
    std::vector<int> result = find_subset(l, u, w);
    
    
    printf("%d\n", (int)result.size());
    for (int i = 0; i < (int)result.size(); i++)
        printf("%d%c", result[i], " \n"[i == (int)result.size() - 1]);
}*/
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...