Submission #543443

#	Time	Username	Problem	Language	Result	Execution time	Memory
543443		NemanjaSo2005	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	48 ms	3960 KiB

molecules

#include<bits/stdc++.h>
#include "molecules.h"
#define ll long long
using namespace std;
ll N,zbir;
struct slog{
  int org,vred;
}sniz[5000005];
bool cmp(slog a,slog b){
  return a.vred<b.vred;
}
vector<int> find_subset(int L, int R, vector<int> niz){
    N=niz.size();
    for(int i=1;i<=N;i++){
      sniz[i].org=i-1;
      sniz[i].vred=niz[i-1];
    }
    sort(sniz+1,sniz+1+N,cmp);
    int i=1,j=1;
    zbir=sniz[1].vred;
    while(j<=N){
      if(i>j)
         break;
      if(zbir<L){
        j++;
        zbir+=sniz[j].vred;
      }
      else if(zbir>R){
        zbir-=sniz[i].vred;
        i++;
      }
      if(zbir<=R and zbir>=L){
         niz.clear();
         for(int k=i;k<=j;k++)
            niz.push_back(sniz[k].org);
         return niz;
      }
    }
    niz.clear();
    return niz;
}

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