제출 #533058

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
533058		safaricola	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	79 ms	8880 KiB

molecules

#include "molecules.h"
#include<bits/stdc++.h>
using namespace std;
long long 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;
    long long low=0, high=n;
    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+1; 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-1]);
            }
            for(int j=n-high+i+1; j<=n; j++){
                v.push_back(id[j-1]);
            }
            return v;
        }
    }
    return vector<int>(0);
}

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