Submission #170428

#	Time	Username	Problem	Language	Result	Execution time	Memory
170428		AlexLuchianov	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	85 ms	6520 KiB

molecules

#include "molecules.h"
#include <algorithm>

using ll = long long;

int const nmax = 200000;

int v[1 + nmax];
int seen[1 + nmax], ind[1 + nmax];

bool compare(int x, int y){
  return v[x] < v[y];
}

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
  std::vector<int> sol;
  int n = w.size();
  for(int i = 0; i < n; i++)
    v[i] = w[i];
  for(int i = 0; i < n; i++)
    ind[i] = i;
  std::sort(ind, ind + n, compare);

  ll sum1 = 0, sum2 = 0;

  for(int i = 0; i < n; i++){
    int pos1 = ind[i], pos2 = ind[n - 1 - i];

    seen[pos1] = 1;
    sum1 += w[pos1];
    sum2 += w[pos2];

    if(sum1 <= u && l <= sum2){
      int ptr = 0;
      while(sum1 < l){
        seen[ind[ptr]] = 0;
        seen[ind[n - 1 - ptr]] = 1;
        sum1 -= w[ind[ptr]];
        sum1 += w[ind[n - 1 - ptr]];
        ptr++;
      }
      for(int i = 0; i < n; i++)
        if(seen[i] == 1)
          sol.push_back(i);
      return sol;
    }
  }
  return sol;
}

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