Submission #395157

#	Time	Username	Problem	Language	Result	Execution time	Memory
395157		ZenWoR	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	105 ms	14924 KiB

molecules

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
//#include "molecules.h"

#define ll long long
#define ar array<int>
#define pb(x) push_back(x)
#define all(x) x.begin(),x.end()

using namespace std;

//https://oj.uz/problem/view/IOI16_molecules

vector<vector<int>> ww;

vector<int> find_subset(int l, int u, vector<int> w) {
  int N=w.size();
  vector<int> ans;
  ll sumall=0;
  for(int i=0;i<N;i++) {
    sumall+=w[i];
    if(l<=w[i] and w[i]<=u) {
      ans.pb(i);
      return ans;
    }
    ww.push_back({w[i],i});
  }
  sort(ww.begin(),ww.end());
  if(l<=sumall and sumall<=u) {
    for(int i=0;i<N;i++)
      ans.pb(i);
    return ans;
  }

  if(sumall<l or ww[0][0]>l)
    return {};

  int L=0,R=0;
  ll sum=0;
  while(R<N) {
    while(R<N) {
      sum+=ww[R++][0];
      if(sum>=l)
        break;
    }
    if(sum>=l and sum<=u) {
      for(int i=L;i<R;i++)
        ans.pb(ww[i][1]);
      return ans;
    }
    while(L<R) {
      sum-=ww[L++][0];
      if(sum<=u)
        break;
    }
    if(sum>=l and sum<=u) {
      for(int i=L;i<R;i++)
        ans.pb(ww[i][1]);
      return ans;
    }
  }

  while(sum>u and L<N)
    sum-=ww[L++][1];
  if(sum>=l and sum<=u) {
    for(int i=L;i<R;i++)
      ans.pb(ww[i][1]);
    return ans;
  }
  return {};
}

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