Submission #770806

#	Time	Username	Problem	Language	Result	Execution time	Memory
770806		perchuts	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	47 ms	7336 KiB

molecules

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include "molecules.h"

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 3e5+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }


std::vector<int> find_subset(int l, int u, std::vector<int> w) {
      vector<pair<ll, int>> v;
      int n = sz(w);
      for (int i = 0; i < n; ++i) v.pb({w[i], i});
      sort(all(v));
      vector<ll> pref(n);
      pref[0] = v[0].first;
      for (int i = 1; i < n; ++i) pref[i] = pref[i-1] + v[i].first;
      vector<int> ans;
      for (int i = 0; i < n; ++i) {
            ll mn = pref[i], mx = pref[n - 1] - (i == n - 1 ? 0 : pref[n - 2 - i]);
            if (l <= mn && mn <= u) {
                  for (int j = 0; j <= i; ++j) ans.pb(v[j].second);
                  return ans;
            }
            if (l <= mx && mx <= u) {
                  for (int j = n - 1 - i; j <= n - 1; ++j) ans.pb(v[j].second);
                  return ans;
            }
            if (mn < l && u < mx) {
                  // there is a good sum somewhere
                  ll sum = mn, j = i;
                  for (; j >= 0; --j) {
                        if (sum - v[j].first + v[n - 1 - i + j].first < l) {
                              ans.pb(v[n - 1 - i + j].second);
                              sum += - v[j].first + v[n - 1 - i + j].first;
                        } else break;
                  }
                  for (int k = 0; k < j; ++k) ans.pb(v[k].second);
                  while (sum < l) sum += -v[j].first + v[j+1].first, j++;
                  assert(l <= sum && sum <= u);
                  ans.pb(v[j].second);
                  return ans;
            }
      }
      // no answer found
      return ans;
}

// int main() {
//     int n, l, u;
//     assert(3 == scanf("%d %d %d", &n, &l, &u));
//     std::vector<int> w(n);
//     for (int i = 0; i < n; i++)
//         assert(1 == scanf("%d", &w[i]));
//     std::vector<int> result = find_subset(l, u, w);
    
    
//     printf("%d\n", (int)result.size());
//     for (int i = 0; i < (int)result.size(); i++)
//         printf("%d%c", result[i], " \n"[i == (int)result.size() - 1]);
// }

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