Submission #276394

#	Time	Username	Problem	Language	Result	Execution time	Memory
276394		arayi	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	66 ms	6776 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define lli long long int
#define MP make_pair
using namespace std;
const int N = 2e5 + 30;
int n;
lli pr[N];
pair <lli, int> a[N];
vector <int> pat;
vector<int> find_subset(int l, int u, vector<int> w)
{
    int n = w.size();
    for (int i = 0; i < n; i++)
        a[i + 1] = MP(w[i], i);
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++)
    {
        pr[i] = a[i].fr;
        pr[i] += pr[i - 1];
    }
    if(pr[n] < l) return pat;
    int l1 = n, r1 = n;
    while(pr[n] - pr[l1 - 1] < l) l1--;
    while(l1 > 0 && pr[r1] - pr[l1 - 1] > u) r1--, l1--;
    if(l1 == 0) return pat;
    for (int i = l1; i <= r1; i++)
    {
        pat.push_back(a[i].sc);
    }
    return pat;
}

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