Submission #314614

#	Time	Username	Problem	Language	Result	Execution time	Memory
314614		Dymo	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	62 ms	8696 KiB

molecules

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


#define pb	push_back
#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"
const ll maxn=4e5+50;
const ll mod =1e9+7;
const ll base=517;
pll a[maxn];
ll f[maxn];

vector<int> find_subset(int l, int u, vector<int>w)
{
    ll n=w.size();
    for (int i=0;i<n;i++)
    {
        a[i].ff=w[i];
        a[i].ss=i;
    }
    sort(a,a+n);
    for (int i=0;i<n;i++)
    {
        if (i) f[i]=f[i-1]+a[i].ff;
        else f[i]=a[i].ff;
    }
    for (int i=1;i<=n;i++)
    {
         if (f[i-1]>=l&&f[i-1]<=u)
         {
             vector<int>ans1;
             for (int j=0;j<i;j++)
             {
                 ans1.pb(a[j].ss);
             }
             sort(ans1.begin(),ans1.end());
            return ans1;

         }
         else if (f[i-1]<l&&i!=n&&f[n-1]-f[n-1-i]>=l)
         {
             ll t1=i-1;
             ll t2=n;
             ll ans=f[i-1];
             while (t1>=0&&ans<l)
             {
                  ans-=a[t1].ff;
                  t1--;
                  t2--;
                  ans+=a[t2].ff;
             }
             vector<int>ans1;
             ll m=i;
             for (int j=0;j<m;j++)
             {
                if (t1>=0)
                {
                   ans1.pb(a[t1].ss);

                    t1--;
                }
                else if (t2<n)
                {
                     ans1.pb(a[t2].ss);
                    t2++;

                }
             }
             sort(ans1.begin(),ans1.end());
            return ans1;


         }
    }
    vector<int> ans1;
    return ans1;
}
/*int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("GIDDY.inp", "r"))
    {
        freopen("GIDDY.inp", "r", stdin);
        freopen("GIDDY.out", "w", stdout) ;
    }

}*/

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