Submission #1093293

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093293		Frostidian	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	44 ms	10428 KiB

molecules

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

vector < int > find_subset ( int left, int right, vector < int > y ){
    long long n = y.size();
    vector < long long > pref ( n + 5 ), suf ( n + 5 );
    vector < pair < long long, long long >> a ( n + 5 );

    for ( int i = 1; i <= n; i++ ) a[i].first = y[i - 1], a[i].second = i - 1;

    sort ( a.begin() + 1, a.begin() + 1 + n );

    for ( int i = 1; i <= n; i++ ) pref[i] = pref[i - 1] + a[i].first;
    for ( int i = n; i >= 1; i-- ) suf[i] = suf[i + 1] + a[i].first;
    vector < int > ans;

    for ( int i = n + 1; i >= 1; i-- ){
        int l = 1, r = i - 1, rec = 0;
        while ( l <= r ){
            int mid = ( l + r ) / 2;
            if ( pref[mid] + suf[i] <= left ){
                l = mid + 1;
                rec = mid;
            }
            else r = mid - 1;
        }

        if ( pref[rec] + suf[i] >= left && pref[rec] + suf[i] <= right ){
            for ( int j = 1; j <= rec; j++ ){
                ans.push_back(a[j].second);
            }

            for ( int j = n; j >= i; j-- ){
                ans.push_back(a[j].second);
            }

            sort ( ans.begin(), ans.end());

            return ans;
        }

        if ( rec + 1 <= i - 1 ){
            rec++;
            if ( pref[rec] + suf[i] >= left && pref[rec] + suf[i] <= right ){
                for ( int j = 1; j <= rec; j++ ){
                    ans.push_back(a[j].second);
                }

                for ( int j = n; j >= i; j-- ){
                    ans.push_back(a[j].second);
                }

                sort ( ans.begin(), ans.end());

                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