Submission #987592

#	Time	Username	Problem	Language	Result	Execution time	Memory
987592		LucaIlie	Detecting Molecules (IOI16_molecules)	C++17	69 / 100	27 ms	6592 KiB

molecules

#include "molecules.h"
#include <iostream>
#include <algorithm>

using namespace std;

#define nmax 200001

struct info{
    int val, poz;
    bool operator < ( info const & x ) const {
        return val < x.val;
    }
};

info v[nmax];
int minn[nmax], maxx[nmax];
vector <int> rasp;

vector<int> find_subset( int l, int u, vector<int> w ) {
    int n, i, j, s, k;
    n = w.size();
    for( i = 1; i <= n; i++ ) {
        v[i].val = w[i - 1];
        v[i].poz = i - 1;
    }
    sort( v + 1, v + n + 1 );
    for( i = 1; i <= n; i++ ) {
        minn[i] = minn[i - 1] + v[i].val;
        maxx[i] = maxx[i - 1] + v[n + 1 - i].val;
    }

    for( i = 1; i <= n; i++ )
        if( ( minn[i] >= l && minn[i] <= u ) ||  ( maxx[i] >= l && maxx[i] <= u ) || ( minn[i] <= l && maxx[i] >= u ) )
            break;
    if( i == n + 1 )
        return rasp;
    //cout << minn[i] << " " << maxx[i] << "\n";
    s = minn[i] - v[i].val;
    for( j = 0; j < n - i + 1; j++ ) {
        s = s + v[j + i].val - v[j].val;
        if( l <= s && s <= u )
            break;
    }
    for( k = j + 1; k < j + i + 1; k++ )
        rasp.push_back( v[k].poz );
    //cout << i << " " << j << " " << s << "\n";
    return rasp;
}

/*
4 10 20
15 17 16 18
 */

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