Submission #555950

#	Time	Username	Problem	Language	Result	Execution time	Memory
555950		pere_gil	Detecting Molecules (IOI16_molecules)	C++14	19 / 100	1087 ms	524 KiB

molecules

#include "molecules.h"
#include "bits/stdc++.h"
using namespace std;

#define ii pair<long long,long long>
typedef long long ll;
int MAX_N=1005;
vector<vector<ll> > ma(MAX_N,vector<ll> (1,0));
vector<int> res;

void solve(int l, int r, ll pos, vector<ii> &v, ll &sum){
	if(pos==MAX_N){
		if(sum<l || sum>r) return;
		res.clear();
		for(int i=0;i<v.size();i++)
			for(int j=1;j<=v[i].first;j++)
				res.push_back(ma[v[i].second][j]);
		/*
		printf("end with %lld\n",sum);
		for(int i=0;i<res.size();i++) printf("%d ",res[i]); printf("\n");
		for(int i=0;i<v.size();i++) printf("%lld ; %lld\n",v[i].first,v[i].second);
		printf("\n");
		*/
		return;
	}
	for(ll i=0;i<ma[pos].size();i++)
		if(sum+i*pos<=r){
			sum+=i*pos;
			v.push_back({i,pos});
			solve(l,r,pos+1,v,sum);
			sum-=i*pos;
			v.pop_back();
		}
}

vector<int> find_subset(int l, int r, vector<int> w) {
	int n=w.size();
	for(int i=0;i<n;i++)
		ma[w[i]].push_back(i);

	vector<ii> v;
	ll sum=0;
	solve(l,r,1,v,sum);
	
	return res;
}

Compilation message (stderr)

molecules.cpp: In function 'void solve(int, int, ll, std::vector<std::pair<long long int, long long int> >&, ll&)':
molecules.cpp:15:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |   for(int i=0;i<v.size();i++)
      |               ~^~~~~~~~~
molecules.cpp:26:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(ll i=0;i<ma[pos].size();i++)
      |             ~^~~~~~~~~~~~~~~

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