Submission #227608

#	Time	Username	Problem	Language	Result	Execution time	Memory
227608		AASG	Detecting Molecules (IOI16_molecules)	C++11	0 / 100	5 ms	384 KiB

molecules

#include<bits/stdc++.h>
#include "molecules.h"
using namespace std;
 vector<int> find_subset(int l, int u, vector<int> w) {
    int n=w.size();int r1=0,r2=0;
    vector<pair<long long,int> >r;
    vector<int> rr;
    for(int i=0;i<n;i++){
        r.push_back(make_pair(w[i],i));
    }
    sort(r.begin(),r.end());
    long long int A[n];
    A[0]=r[0].first;
    for(int i=1;i<n;i++)A[i]=A[i-1]+r[i].first;
    long long rt=0;
    int p1=0,p2=n-1;bool x=true;
    for(int i=n-1;i>=0 && x;i--){
        p1=-1;p2=i;int p3;
        while(abs(p1-p2)!=1){
            p3=(p1+p2)/2;
            if(A[i]-A[p3]>=l && A[i]-A[p3]<=u){
            r1=i;r2=p3;x=false;break;
            }
            else if(A[i]-A[p3]>u){p1=p3;}
            else if(A[i]-A[p3]<l){p2=p3;}
        }

    }
    for(int i=min(r1,r2)+1;i<=max(r1,r2);i++){
        rr.push_back(r[i].second);
    }
    sort(rr.begin(),rr.end());
    return rr;
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:15:15: warning: unused variable 'rt' [-Wunused-variable]
     long long rt=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