Submission #805240

#	Time	Username	Problem	Language	Result	Execution time	Memory
805240		erray	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	39 ms	5548 KiB

molecules

#include "molecules.h"
#include<bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/ioi/codes/ioi16_d1/debug.h"
#else 
  #define debug(...) void(37)
#endif

std::vector<int> find_subset(int L, int U, std::vector<int> W) {
  int N = int(W.size());  
  vector<int> ord(N);
  iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), [&](int x, int y) {
    return W[x] < W[y];
  });
  vector<int> nw(N);
  for (int i = 0; i < N; ++i) {
    nw[i] = W[ord[i]]; 
  } 
  swap(W, nw);
  debug(W, ord);
  long long sum = 0;
  int p = -1;
  vector<int> res;
  while (p < N - 1 && sum + W[p + 1] <= U) {
    ++p;
    sum += W[p];
    res.push_back(p);
  }
  for (int i = p; i >= 0; --i) {
    int next = W[N - 1 - (p - i)];
    res.pop_back();
    if (sum + next - W[i] >= L) {
      int add = i;
      while (sum < L) {
        sum += W[add + 1] - W[add];
        ++add;
      }
      assert(L <= sum && sum <= U);
      res.push_back(add);
      break;
    } else {
      sum += next - W[i];
    }
  }
  debug(res);
  if (sum < L || U < sum) {
    return vector<int>{};
  }
  for (int i = p - int(res.size()); i >= 0; --i) {
    res.push_back(N - 1 - i);
  }
  for (auto& x : res) {
    x = ord[x];
  }
  sort(res.begin(), res.end());
  return res;
}

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