Submission #172068

#	Time	Username	Problem	Language	Result	Execution time	Memory
172068		arnold518	Detecting Molecules (IOI16_molecules)	C++14	69 / 100	1072 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);

    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;

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

        for(j=i; j>=1; j--)
        {
            if(p-A[j].first+A[N-i+j].first<L)
            {
                p=p-A[j].first+A[N-i+j].first;
                continue;
            }
            for(k=j+1; k<=N-i+j; k++)
            {
                p+=A[k].first-A[k-1].first;
                if(L<=p)
                {
                    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;
                }
            }
            assert(0);
        }
        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