Submission #823813

#	Time	Username	Problem	Language	Result	Execution time	Memory
823813		vnm06	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	38 ms	7124 KiB

molecules

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


pair<int, int> pr[200005];
long long prfs[200005];

std::vector<int> find_subset(int l, int u, std::vector<int> w)
{
    vector<int> res;
    res.resize(0);

    int n=w.size();
    for(int i=0; i<n; i++)
    {
        pr[i]={w[i], i};
    }
    sort(pr, pr+n);
    prfs[0]=pr[0].first;
    int id=-1;
    if(w[0]>u) return res;
    if(w[0]>=l)
    {
        res.push_back(pr[0].second);
        return res;
    }
    for(int i=1; i<n; i++) prfs[i]=prfs[i-1]+pr[i].first;
    if(prfs[n-1]>=l && prfs[n-1]<=u)
    {
        for(int i=0; i<n; i++) res.push_back(i);
        return res;
    }
    for(int i=2; i<n; i++)
    {
        if(prfs[i-1]<=u && prfs[n-1]-prfs[n-i-1]>=l)
        {
            int j=i;
            while(j>=0)
            {
                if(prfs[j-1]+prfs[n-1]-prfs[n-i+j-1]>=l) break;
                j--;
            }
            for(int k=0; k<j; k++) res.push_back(pr[k].second);
            for(int k=n-1; k>=n-i+j; k--) res.push_back(pr[k].second);
            return res;
        }
    }
    return res;
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:21:9: warning: unused variable 'id' [-Wunused-variable]
   21 |     int id=-1;
      |         ^~

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