Submission #443862

#	Time	Username	Problem	Language	Result	Execution time	Memory
443862		Khizri	Detecting Molecules (IOI16_molecules)	C++17	31 / 100	1075 ms	5640 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back		 
#define F first																 
#define S second 															 
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
#define endl "\n"
const int mxn=2e5+5;
vector<pii>dp[mxn];
map<int,bool>mp;
std::vector<int> find_subset(int l, int r, std::vector<int> vt) {
	bool q=false;
	int ans=-1,ind=-1;
    for(int i=0;i<vt.size();i++){
    	dp[i].pb({vt[i],-1});
    	if(l<=vt[i]&&vt[i]<=r){
    		return {i};
		}
		for(int j=0;j<i;j++){
			for(int k=0;k<dp[j].size();k++){
				if(!mp[dp[j][k].F+vt[i]]&&dp[j][k].F+vt[i]<=r){
					dp[i].pb({dp[j][k].F+vt[i],j});
					mp[dp[j][k].F+vt[i]]=true;
				}
				if(l<=dp[j][k].F+vt[i]&&dp[j][k].F+vt[i]<=r){
					ans=dp[j][k].F+vt[i];
					ind=i;
					q=true;
					goto loopo;
				}
			}
		}
	}
	loopo:
	vector<int>v;
	if(!q){
		return v;
	}
	while(ind!=-1){
		//cout<<ans<<' '<<ind<<endl;
		v.pb(ind);
		//cout<<dp[ind].size()<<endl;
		for(int i=0;i<dp[ind].size();i++){
			//cout<<dp[ind][i].F<<' ';
			if(dp[ind][i].F==ans){
				ans-=vt[ind];
				ind=dp[ind][i].S;
				break;
			}
		}
		//cout<<endl;
	}
	//cout<<0<<endl;
	sort(all(v));
	return v;
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0;i<vt.size();i++){
      |                 ~^~~~~~~~~~
molecules.cpp:28:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |    for(int k=0;k<dp[j].size();k++){
      |                ~^~~~~~~~~~~~~
molecules.cpp:51:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for(int i=0;i<dp[ind].size();i++){
      |               ~^~~~~~~~~~~~~~~

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