Submission #74654

#	Time	Username	Problem	Language	Result	Execution time	Memory
74654		kjain_1810	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	80 ms	15088 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
using namespace std;

typedef long long ll;

vector< pair<ll, ll> >vec;
ll u, l;

std::vector<int> find_subset(int L, int U, std::vector<int> w) {
    for(ll a=0; a<w.size(); a++)
    	vec.pb({w[a], a});
    sort(vec.begin(), vec.end());
    ll ptrf=0, sum=0, u=U, l=L, ptrb=0;
    bool flag=false;
    while(ptrf<vec.size())
    {
    	while(ptrf<vec.size() && sum<l)
    	{
    		sum+=vec[ptrf].f;
    		ptrf++;
    	}
    	if(sum<=u && sum>=l)
    	{
    		vector<int>ret;
    		ret.clear();
    		for(int a=ptrb; a<ptrf; a++)
    			ret.pb(vec[a].s);
    		return ret;
    	}
    	while(ptrb<ptrf && sum>u)
    	{
    		sum-=vec[ptrb].f;
    		ptrb++;
    	}
    	if(sum<=u && sum>=l)
    	{
    		vector<int>ret;
    		ret.clear();
    		for(int a=ptrb; a<ptrf; a++)
    			ret.pb(vec[a].s);
    		return ret;
    	}
    }
    int x=0;
    for(int a=vec.size()-1; a>=0; a--)
    {
    	x+=vec[a].f;
    	if(sum<=u && sum>=l)
    	{
    		vector<int>ret;
    		ret.clear();
    		for(; a<vec.size(); a++)
    			ret.pb(vec[a].s);
    		return ret;
    	}
    }
    x=0;
    for(int a=0; a<vec.size(); a--)
    {
    	x+=vec[a].f;
    	if(sum<=u && sum>=l)
    	{
    		vector<int>ret;
    		ret.clear();
    		for(; a>=0; a--)
    			ret.pb(vec[a].s);
    		return ret;
    	}
    }
    vector<int>ret;
    ret.clear();
    return ret;
    // for(ll a=1; a<vec.size(); a++)
    // {
    // 	if(sum<=u && sum>=l)
    // 	{
    // 		flag=true;
    // 		ptr2=a;
    // 		break;
    // 	}
    // 	sum+=vec[a].f;
    // 	if(sum<=u && sum>=l)
    // 	{
    // 		flag=true;
    // 		ptr2=a+1;
    // 		break;
    // 	}
    // 	while(sum>u)
    // 	{
    // 		sum-=vec[ptr].f;
    // 		ptr++;
    // 	}
    // }
    // if(!flag)
    // {
    // 	vector<int>yo;
    // 	yo.clear();
    // 	return yo;
    // }
    // vector<int>yo;
    // for(ll b=ptr; b<ptr2; b++)
    // {
    // 	yo.pb(w[vec[b].s]);
    // }
    // return yo;
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:14:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll a=0; a<w.size(); a++)
                 ~^~~~~~~~~
molecules.cpp:19:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ptrf<vec.size())
           ~~~~^~~~~~~~~~~
molecules.cpp:21:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      while(ptrf<vec.size() && sum<l)
            ~~~~^~~~~~~~~~~
molecules.cpp:56:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(; a<vec.size(); a++)
             ~^~~~~~~~~~~
molecules.cpp:62:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int a=0; a<vec.size(); a--)
                  ~^~~~~~~~~~~
molecules.cpp:18:10: warning: unused variable 'flag' [-Wunused-variable]
     bool flag=false;
          ^~~~

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