Submission #312232

#	Time	Username	Problem	Language	Result	Execution time	Memory
312232		Nayna	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	66 ms	6884 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>

using namespace std;

const int mxn = 1e5+5;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<ll,ll>pii;
typedef pair<int,pii>piii;

#define  sf scanf
#define  pf printf

#define  input freopen("in.txt","r",stdin)
#define  output freopen("out.txt","w",stdout)

#define  inf 1e16
#define  ff first
#define  ss second
#define  MP make_pair
#define  pb push_back
#define  all(v) v.begin(), v.end()
#define  printcase(cases) printf("Case %d:", cases);
#define  Unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define  FAST  ios_base::sync_with_stdio(0);cout.tie(0)
//#define  endl printf("\n")
#define  __lcm(a, b) ((a*b)/__gcd(a, b))


vector<int> find_subset(int l, int u, vector<int> w)
{
    int n = w.size();
    vector<pii>arr;
    for(int i = 0; i < n; i++) arr.push_back({w[i], i});
    sort(all(arr));
    ll pre[n+10];
    pre[0] = arr[0].ff;
    for(int i = 1; i < n; i++) pre[i] = pre[i-1]+arr[i].ff;
    vector<int>res;
    for(int i = 0; i < n; i++)
    {
        int lo = i, hi = n-1;
        while(lo<=hi)
        {
            int mid = (lo+hi)>>1;
            int r = mid;
            ll sum = 0;
            if(i==0) sum = pre[r];
            else sum = pre[r]-pre[i-1];
            if(sum>u) hi = mid-1;
            else if(sum<l) lo = mid+1;
            else if(sum>=l && sum<=u)
            {
                for(int j = i; j <= r; j++) res.push_back(arr[j].ss);
                return res;
            }

        }
    }
    return res;
}

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