Submission #533049

#	Time	Username	Problem	Language	Result	Execution time	Memory
533049		safaricola	Detecting Molecules (IOI16_molecules)	C++17	0 / 100	1 ms	304 KiB

molecules

#include "molecules.h"
#include<bits/stdc++.h>
using namespace std;
int L,U,n,a[200010],id[200020],pre[200010],su[200010];
bool cmp(int x, int y){
    return a[x]<a[y];
}
vector<int> find_subset(int l, int u, vector<int> w) {
    n=w.size();
    for(int i=0; i<n; i++){
        a[i]=w[i];
        id[i]=i;
    }
    sort(id, id+n, cmp);
    //for(int i=0; i<n; i++)cout<<id[i]<<" ";
    //    cout<<endl;
    for(int i=1; i<=n; i++){
        pre[i]=pre[i-1]+a[id[i-1]];
    }
    for(int i=n; i>=1; i--){
        su[i]=su[i+1]+a[id[i-1]];
    }
    //for(int i=1; i<=n; i++) cout<<su[i]<<" ";
    //   cout<<endl;
    int low=0, high=n+1;
    while(high - low >= 2){
        int mid = (high + low) / 2;
        if(pre[mid]>=l) high = mid;
        else low = mid;
    }
    //printf("%d, %d \n",high, low);
    high=low;
    for(int i=0; i<high; i++){
        //cout<<pre[i]+su[n-high+i+1]<<" "<<(pre[i]+su[n-high+i+1]>=l)<<" "<<(pre[i]+su[n-high+i+1]<=u)<<endl;
        if(pre[i]+su[n-high+i+1]>=l&&pre[i]+su[n-high+i+1]<=u){
            vector<int> v;
            for(int j=1; j<=i; j++){
                v.push_back(id[j]);
            }
            for(int j=n-high+i+1; j<=n; j++){
                v.push_back(id[j]);
            }
            return v;
        }
    }
    return vector<int>(0);
}

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