제출 #898423

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
898423		duckindog	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	41 ms	6324 KiB

molecules

// from duckindog wth depression
#include<bits/stdc++.h>

using namespace std;

//#define LOCAL

#ifndef LOCAL
#include "molecules.h"
#endif // LOCAL

const int N = 5e5 + 10;;

vector<int> find_subset(int l, int u, vector<int> w) {

  int n = w.size();
  using pii = pair<int, int>;
  vector<pii> d;
  for (int i = 0; i < n; ++i) d.push_back({w[i], i});
  sort(d.begin(), d.end());
  deque<int> q;
  long long sum = 0;
  for (int i = 0; i < n; ++i) {
    int x, j; tie(x, j) = d[i];
    sum += x;
    q.push_back(j);
    if (sum >= l && sum <= u) break;
    while (sum >= u) {
      sum -= w[q.front()];
      q.pop_front();
    }
    if (sum >= l && sum <= u) break;
  }

  if (sum < l) return {};
  vector<int> answer;
  while (q.size()) {
    answer.push_back(q.back());
    q.pop_back();
  }
  return answer;
}

#ifdef LOCAL
int32_t main() {
  cin.tie(0)->sync_with_stdio(0);

  if (fopen("duck.inp", "r")) {
    freopen("duck.inp", "r", stdin);
    freopen("duck.out", "w", stdout);
  }

  int l, u; cin >> l >> u;
  int x;
  vector<int> input;
  while (cin >> x) input.push_back(x);

  for (auto i : find_subset(l, u, input))
    cout << i << ' ';
}
#endif // LOCAL

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