Submission #1244236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244236		greenbinjack	Detecting Molecules (IOI16_molecules)	C++20	100 / 100	35 ms	4028 KiB

molecules

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
 
#include <bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
using LL = long long;
 
#define all(V) V.begin(), V.end()
 
template <typename DT> using ordered_set = tree <DT, null_type, less <DT>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename DT> using minheap = priority_queue < DT, vector <DT>, greater <DT> >;
template <class T> bool chMax (T &x, T y) { return y > x ? x = y, 1 : 0; }
template <class T> bool chMin (T &x, T y) { return y < x ? x = y, 1 : 0; }

#include "molecules.h"

vector<int> find_subset(int l, int u, vector<int> w) {
  int n = w.size ();
  vector < pair <int, int> > v;
  for (int i = 0; i < n; i++) v.emplace_back (w[i], i);
  sort (all (v));
  LL li = 0, sum = 0;
  for (int ri = 0; ri < n; ri++) {
    sum += v[ri].first;
    while ((li < ri and v[ri].first - v[li].first > u - l) or sum > u) {
      sum -= v[li++].first;
    }
    if (sum >= l and sum <= u) {
      vector <int> ans;
      for (int j = li; j <= ri; j++) ans.emplace_back (v[j].second);
      sort (all (ans));
      return ans;
    }
  }
  return {};
}

// int main() {
//   cin.tie (nullptr) -> ios_base :: sync_with_stdio (false);

//   auto ans = find_subset(10, 20, {15, 17, 16, 18});
//   for (auto c : ans) cerr << c << endl;

//   return 0;   
// } 

Compilation message (stderr)

molecules.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
molecules_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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