Submission #990814

#	Time	Username	Problem	Language	Result	Execution time	Memory
990814		ChottuF	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	36 ms	7268 KiB

molecules

  #include "molecules.h"
  #include <bits/stdc++.h>
  using namespace std;

  vector<int> find_subset(int l, int u, vector<int> w) {
      long long n = w.size();
      vector<pair<long long,long long>> vec(n);
      for (long long i = 0; i<n; i++){
          vec[i] = {w[i],i};
      }
      sort(vec.begin(),vec.end());
      vector<bool> vis(n);
      long long pt = n-1;
      long long cr = 0;
      while (pt >= 0){
          if (cr < l){
              cr += vec[pt].first;
              vis[pt] = true;
              pt--;
          }
          if (pt < 0) break;
          if ((l <= cr) && (cr <= u)){
              break;
          }
          int lm = pt;
          //can go from 0...pt, and pt+1,...,n-1
          int o = 0;
          int r = n-1;
          bool dul = false;
          while (cr > u){
              dul = true;
              if (o > pt) break;
              if (r < pt+1) break;
              if (!(o<r)) break;
              cr -= vec[r].first;
              cr += vec[o].first;
              vis[r] = false;
              vis[o] = true;
              r--;
              o++;
          }
          if (dul) break;
          if ((l <= cr) && (cr <= u)) break;
      }
      vector<int> ans;
      if (cr < l || cr > u){
          return ans;
      }
      else{
          for (long long i = 0; i<n; i++){
              if (vis[i]){
                  ans.push_back(vec[i].second);
              }
          }
          return ans;
      }
  }

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:25:15: warning: unused variable 'lm' [-Wunused-variable]
   25 |           int lm = pt;
      |               ^~

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