Submission #1163396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163396		Aza	Detecting Molecules (IOI16_molecules)	C++20	9 / 100	1 ms	328 KiB

molecules

//AzaLE (Azamat Alisherov)
#include <bits/stdc++.h>
#include "molecules.h"
#define F first
#define S second
#define size(x) (int)x.size()
using namespace std;
vector <int> find_subset(int l, int r, vector<int> v){
	set<pair<int, int>> st; 
	//using set so no two identical values appear while searching within L and R
	//st.F is value;
	//st.S is index;
	vector <int> inds(size(v));
	//using this vector to retrieve answer if it exists-
	//-via backtracking indexes
	st.insert({0, -1});
	for(int i = 0; i < size(v); i++){
		int mn = l - v[i];
		//searching for appropriate minimum "adder" for L;
		auto it = st.lower_bound({mn, -1});
		if(it == st.end())it--;
		//cout << v[i] << "----> " << mn << " " << (*it).F << " " << (*it).S << endl;
		pair<int, int> ins;
		ins.F = (*it).F + v[i];
		inds[i] = (*it).S;
		ins.S = i;
		st.insert({v[i], i});
		if(ins.F > r)continue;
		st.insert(ins);
	}
	//for(auto [a, b]:st)cout << a << " " << b << endl;
	auto it = st.lower_bound({l, -1});
	int stind = -1;
	//stind (starting index) to backtrack the answer
	if((*it).F >= l and (*it).F <= r){
		stind = (*it).S;
	}
	for(int i = 0; i < size(v); i++){
		if(v[i] >= l and v[i] <= r){
			return {i};
		}
	}
	if(stind == -1){
		return {};
	}
	vector <int> ans;
	while(stind >= 0){
		ans.push_back(stind);
		stind = inds[stind];
	}
	int res = 0;
	for(int i = 0; i < size(ans); i++){
		res += v[ans[i]];
	}
	while(res > r){
		res -= v[ans.back()];
		ans.pop_back();
	}
	return ans;
}
/*

*/

Compilation message (stderr)

molecules.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
molecules_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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