Submission #101797

#	Time	Username	Problem	Language	Result	Execution time	Memory
101797		baluteshih	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	84 ms	6472 KiB

molecules

#include "molecules.h"
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define pb push_back
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define F first
#define S second
#define ET cout << "\n"
#define MP make_pair
#define MEM(i,j) memset(i,j,sizeof i)
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

vector<int> find_subset(int l, int u, vector<int> w) 
{
	vector<int> ans;
	vector<pll> v;
	for(int i=0;i<w.size();++i)
		v.pb(MP(w[i],i));
	sort(ALL(v));
	ll sum=0,r=0;
	for(int i=0;i<v.size();sum-=v[i].F,++i)
	{
		while(r<v.size()&&v[r].F-v[i].F<=u-l&&sum+v[r].F<=u)
		{
			sum+=v[r].F,++r;
			if(sum>=l)
			{
				for(int j=i;j<r;++j)
					ans.pb(v[j].S);
				return ans;
			}
		}
		if(sum==0) break;
	}
    return ans;
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:22:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<w.size();++i)
              ~^~~~~~~~~
molecules.cpp:26:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v.size();sum-=v[i].F,++i)
              ~^~~~~~~~~
molecules.cpp:28:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(r<v.size()&&v[r].F-v[i].F<=u-l&&sum+v[r].F<=u)
         ~^~~~~~~~~

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