Submission #683424

#	Time	Username	Problem	Language	Result	Execution time	Memory
683424		cadmiumsky	Detecting Molecules (IOI16_molecules)	C++14	46 / 100	4 ms	824 KiB

molecules

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

#define all(x) (x).begin(),(x).end()

using namespace std;

using ll = long long;

#define int ll
#define sz(x) (int)(x).size()
using pii = pair<int,int>;
#undef int
std::vector<int> find_subset(int l, int u, std::vector<int> W) {
  #define int ll
  if(accumulate(all(W), 0) < l) return vector<signed>(0);
  vector<pii> w;
  for(auto x : W)
    w.emplace_back(x, sz(w));
  
  sort(all(w));
  
  if(l <= w.back().first && w.back().first <= u) return vector<signed>(1, w.back().second);
  if(w[0].first > l) return vector<signed>(0);

  vector<signed> rez;
  int sum = 0;
  for(int i = 0; i < sz(w); i++) {
    sum += w[i].first;
    if(sum > u) { sum -= w[i].first; break; }
    rez.emplace_back(w[i].second);
  }
  
  if(l <= sum && sum <= u) return rez;
  
  //cerr << sum << ' ';
  //for(auto x : rez) cerr << x << ' ';
  //cerr << '\n';
  
  vector<signed> replace;
  //cerr << sz(rez) << '\n';
  for(int i = sz(w) - 1; sz(rez) && i >= 0; i--) {
    if(l <= sum && sum <= u) break;
    auto cv = W[rez.back()];
    sum += w[i].first - cv;
    rez.pop_back();
    replace.emplace_back(w[i].second);
    //cerr << sum << ' ';
  }
  if(sum < l) return vector<signed>(0);
  copy(all(replace), back_inserter(rez));
  return rez;
  
}
#undef int

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