Submission #533028

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

molecules

#include "molecules.h"
#include<bits/stdc++.h>
using namespace std;
int L,U,n,a[200010],pre[200010],su[200010];

vector<int> find_subset(int l, int u, vector<int> w) {
    n=w.size();
    for(int i=0; i<n; i++){
        a[i+1]=w[i];
    } 
    sort(a+1, a+n+1);
    for(int i=1; i<=n; i++){
        pre[i]=pre[i-1]+a[i]; 
    }
    for(int i=n; i>=1; i--){
        su[i]=su[i+1]+a[i];
    }
    //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);
    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(j);
            }
            for(int j=n-high+i+1; j<=n; j++){
                v.push_back(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