Submission #499391

#	Time	Username	Problem	Language	Result	Execution time	Memory
499391		LucaIlie	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	47 ms	7084 KiB

molecules

#include <iostream>
#include <vector>
#include <algorithm>

#define MAX_N 200000

using namespace std;

struct val_and_pos {
    int val, pos;
    bool operator < (const val_and_pos &a) const {
        return val < a.val;
    }
};

long long sp[MAX_N + 1];
val_and_pos v[MAX_N + 1];

vector <int> find_subset( int lower, int upper, vector <int> w ) {
    int n, l, i, j;
    vector <int> ans;

    n = w.size();
    for ( i = 1; i <= n; i++ )
        v[i] = { w[i - 1], i - 1 };
    sort( v, v + n + 1 );
    for ( i = 1; i <= n; i++ )
        sp[i] = sp[i - 1] + v[i].val;

    for ( l = 1; l <= n; l++ ) {
        if ( sp[l] <= upper && sp[n] - sp[n - l] >= lower ) {
            for ( i = l; i <= n; i++ ) {
                if ( lower <= sp[i] - sp[i - l] && sp[i] - sp[i - l] <= upper ) {
                    for ( j = i - l + 1; j <= i; j++ )
                        ans.push_back( v[j].pos );
                    return ans;
                }
            }
        }
    }

    return ans;
}

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