Submission #65732

#	Time	Username	Problem	Language	Result	Execution time	Memory
65732		MANcity	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	81 ms	33568 KiB

molecules

#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<cstring>
#include<vector>
#include "molecules.h"
using namespace std;
#define for1(i,n) for(int i=1;i<=(int)n;i++)
#define for0(i,n) for(int i=0;i<=(int)n;i++)
#define forn(i,n) for(int i=n;i>=1;i--)
#define fo(i,x,y) for(int i=x;i<=(int)y;i++)
#define fr(i,x,y) for(int i=x;i>=(int)y;i--)
#define pb push_back
#define mp make_pair
#define LL long long
const LL Mod=1000*1000*1000+7;
vector<int> find_subset(int l, int u, vector<int> w) {
    pair<LL,int> W[200010];
    int used[200010];
    for0(i,200002)
        used[i]=0;
    int n=w.size();
    for0(i,n-1)
        W[i]=mp(w[i],i);
    sort(W,W+n);
    int a=0;
    int b=0;
    LL S=W[0].first;
    used[0]=1;
    while(1)
    {
        if(S>=l && S<=u)
        {
            vector<int> ans;
            for0(i,n-1)
                if(used[i]==1)
                    ans.push_back(W[i].second);
            sort(ans.begin(),ans.end());
            return ans;
        }
        if(S<l)
        {
            if(b==(n-1))
            {
                vector<int> ans(0);
                return ans;
            }
            b++;
            S+=W[b].first;
            used[b]=1;
        }
        if(S>u)
        {
            if(a==b)
            {
                vector<int> ans(0);
                return ans;
            }
            S-=W[a].first;
            used[a]=0;
            a++;
        }
    }
}

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