Submission #853004

#TimeUsernameProblemLanguageResultExecution timeMemory
853004qinDetecting Molecules (IOI16_molecules)C++17
0 / 100
1 ms348 KiB
#include <bits/stdc++.h>
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n");
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
vector<int> find_subset(int L, int R, vector<int> tmp){
		int n = ssize(tmp), it = -1; ll l = L, r = R, sum = 0;
		vector<pli> w(n);
		for(int i = 0; i < n; ++i) w[i] = pli(tmp[i], i);
		sort(w.begin(), w.end());
		if(R < w[0].fi) return vector<int>();
		for(int i = 0; i < n; ++i){
				if(r < sum + w[i].fi){ it = i; break; }
				sum += w[i].fi;
		} // it to dlugosc "dobrego" prefiksu
		vector<int> ans;
		if(l <= sum && sum <= r){
				for(int j = 0; j < it; ++j) ans.emplace_back(w[j].se);
				sort(ans.begin(), ans.end());
				return ans;
		}
		for(int i = it; i < n; ++i){
				sum += w[i].fi - w[i-it].fi;
				if(l <= sum && sum <= r){
						for(int j = i-it+1; j <= it; ++j) ans.emplace_back(w[j].se);
						sort(ans.begin(), ans.end());
						return ans;
				}
		} return vector<int>();
}
#ifdef LOCAL
int main(){
		int n, l, r; scanf("%d%d%d", &n, &l, &r);
		vector<int> w(n);
		for(int i = 0; i < n; ++i) scanf("%d", &w[i]);
		vector<int> out = find_subset(l, r, w);
		for(int u : out) printf("%d ", u);
		pn;
		return 0;
}
#endif
#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...