Submission #20598

#	Time	Username	Problem	Language	Result	Execution time	Memory
20598		model_code	Detecting Molecules (IOI16_molecules)	C11	31 / 100	0 ms	21568 KiB

molecules

// name = molecules_c.c, type = c.gcc
 
#include "molecules_c.h"
// #include "molecules_c.h"
#include <stdlib.h>
 
int *w;
 
int comp(void const *x, void const *y) {
  return w[*(int*)x] - w[*(int*)y];
}
 
int id[5234567];
 
int find_subset(int l, int u, int *w_, int n, int *res) {
  w = w_;
  for (int i = 0; i < n; i++) id[i] = i;
  qsort(id, n, sizeof(int), comp);
  int i = 0;
  long long sum = 0;
  while (i < n && sum + w[id[i]] <= u) {
    sum += w[id[i++]];
  }
  if (sum >= l) {
    for (int j = 0; j < i; j++) res[j] = id[j];
    return i;
  } else {
    int j = 0;
    while (i + j < n && sum < l) {
      sum += w[id[i + j]] - w[id[j]];
      j++;
    }
    if (sum < l) {
      return 0;
    } else {
      for (int t = 0; t < i; t++) {
        res[t] = id[t + j];
      }
      return i;
    }
  }
}
 
 

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