제출 #853011

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
853011		qin	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	41 ms	5208 KiB

molecules

#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
		if(it == -1) it = n;
		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 <= i; ++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

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