Submission #172079

#	Time	Username	Problem	Language	Result	Execution time	Memory
172079		arnold518	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	64 ms	8824 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, L, R;
pii A[MAXN+10];
ll B[MAXN+10], C[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);

    for(i=1; i<=N; i++) B[i]=B[i-1]+A[i].first;
    for(i=N; i>=1; i--) C[i]=C[i+1]+A[i].first;

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

        p=B[i]; q=C[N-i+1];
        if(q<L || R<p) continue;

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

        for(j=i; j>=1; j--)
        {
            if(p-A[j].first+A[N-i+j].first<L)
            {
                p+=A[N-i+j].first-A[j].first;
                continue;
            }
            for(k=j+1; k<=N-i+j; k++)
            {
                p+=A[k].first-A[k-1].first;
                if(L<=p && p<=R)
                {
                    for(l=1; l<j; l++) ans.push_back(A[l].second);
                    ans.push_back(A[k].second);
                    for(l=N-i+j+1; l<=N; l++) ans.push_back(A[l].second);
                    return ans;
                }
            }
        }
    }
    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: 31 / 31