Submission #42710

#	Time	Username	Problem	Language	Result	Execution time	Memory
42710		funcsr	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	69 ms	31788 KiB

molecules

#include "molecules.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define _1 first
#define _2 second

int N;
vector<int> find_subset(int L, int R, vector<int> W) {
  N = W.size();
  vector<P> ps;
  rep(i, N) ps.pb(P(W[i], i));
  sort(all(ps));
  long long lo = 0, hi = 0;
  for (int sz=1; sz<=N; sz++) {
    lo += ps[sz-1]._1;
    hi += ps[N-sz]._1;
    if (max(lo, (long long)L) <= min(hi, (long long)R)) {
      long long sum = lo;
      vector<int> ret(sz);
      rep(i, sz) ret[i] = ps[i]._2;
      int r = N-1;
      for (int i=sz-1; i>=0; i--) {
        if (sum < L) {
          sum += ps[r]._1-ps[i]._1;
          ret[i] = ps[r]._2;
          r--;
        }
      }
      assert(L <= sum && sum <= R);
      return ret;
    }
  }
  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