Submission #1019534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019534		huutuan	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	37 ms	8392 KiB

molecules

#include "molecules.h"

#include <bits/stdc++.h>

using namespace std;

#define int long long

vector<int32_t> find_subset(int32_t l, int32_t u, vector<int32_t> w) {
   vector<pair<int, int>> v;
   int n=w.size();
   for (int i=0; i<n; ++i) v.emplace_back(w[i], i);
   sort(v.begin(), v.end());
   vector<int32_t> ans;
   for (int sz=1, pf=0, sf=0; sz<=n; ++sz){
      pf+=v[sz-1].first;
      sf+=v[n-sz].first;
      if (l<=pf && pf<=u){
         for (int i=0; i<sz; ++i) ans.push_back(v[i].second);
         break;
      }
      if (l<=sf && sf<=u){
         for (int i=n-sz; i<n; ++i) ans.push_back(v[i].second);
         break;
      }
      if (pf<=l && u<=sf){
         int cur=pf, r=n-1;
         for (int i=sz-1; i>=0; --i){
            if (cur+v[r].first-v[i].first<l){
               cur+=v[r].first-v[i].first;
               ans.push_back(v[r].second);
               --r;
            }else{
               int id=i;
               while (cur+v[id].first-v[i].first<l) ++id;
               ans.push_back(v[id].second);
               cur+=v[id].first-v[i].first;
            }
         }
         break;
      }
   }
   return ans;
}

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