Submission #1163388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163388		Aza	Detecting Molecules (IOI16_molecules)	C++20	0 / 100	0 ms	324 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, 0});
		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(ins);
		int mx = r - v[i];
		it = st.lower_bound({mx, 0});
			//searching for appropriate minimum "adder" for R;
			if(it == st.end())it--;
			ins.F = (*it).F + v[i];
			if((*it).S != i){
			inds[i] = (*it).S;
			ins.S = i;
			st.insert(ins);
		}
		st.insert({v[i], -1});
	}
	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;
	}
	it = st.upper_bound({r, -1});
	if(it != st.begin()){
		it--;
	}
	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(inds[stind] > 0){
		ans.push_back(stind);
		stind = inds[stind];
	}
	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: 0 / 9
• Subtask 2: 0 / 10
• Subtask 3: 0 / 12
• Subtask 4: 0 / 15
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31