Submission #172077

#	Time	Username	Problem	Language	Result	Execution time	Memory
172077		arnold518	Detecting Molecules (IOI16_molecules)	C++14	69 / 100	1077 ms	3832 KiB

molecules

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;

int N;
ll L, R;
pll A[MAXN+10];

vector<int> find_subset(int _L, int _R, vector<int> _A)
{
    int i, j, k, l;
    L=_L; R=_R; N=_A.size();
    for(i=1; i<=N; i++) A[i]={_A[i-1], i-1};
    sort(A+1, A+N+1);

    if(L>R) swap(L, R);

    for(i=1; i<=N; i++)
    {
        ll p=0, q=0;

        for(j=1; j<=i; j++) p+=A[j].first;
        for(j=N-i+1; j<=N; j++) q+=A[j].first;

        if(q<L || R<p) continue;

        if(L<=p && p<=R)
        {
            vector<int> ans;
            for(l=1; l<=i; l++) ans.push_back(A[l].second);
            return ans;
        }

        for(j=i; j>=1; j--)
        {
            ll t=p-A[j].first+A[N-i+j].first;
            if(t<L)
            {
                p=p-A[j].first+A[N-i+j].first;
                continue;
            }

            p-=A[j].first;
            int pos=lower_bound(A+j, A+N-i+j+1, pll(L-p, 0))-A;

            vector<int> ans;
            for(k=1; k<j; k++) ans.push_back(A[k].second);
            ans.push_back(A[pos].second);
            for(k=N-i+j+1; k<=N; k++) ans.push_back(A[k].second);
            return ans;
        }
        assert(0);
    }
    return vector<int>();
}

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