Submission #66223

#	Time	Username	Problem	Language	Result	Execution time	Memory
66223		mirbek01	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	107 ms	8592 KiB

molecules

# include "molecules.h"

# include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 2;

long long pref[N];

vector<int> find_subset(int l, int u, vector<int> w) {
      vector <int> ans;
      vector < pair <int, int> > vec;

      for(int i = 0; i < w.size(); i ++){
            vec.push_back({w[i], i});
      }

      sort(vec.begin(), vec.end());

      for(int i = 0; i < vec.size(); i ++){
            if(i)
                  pref[i] = pref[i - 1] + vec[i].first;
            else
                  pref[i] = vec[i].first;
      }

      for(int i = 0; i < vec.size(); i ++){
            int lo = i, hi = vec.size() - 1;
            int L = i - 1;
            if(L < 0) L = vec.size();
            while(hi - lo > 1){
                  int md = (lo + hi) >> 1;
                  if(pref[md] - pref[L] >= l)
                        hi = md;
                  else
                        lo = md;
            }
            if(pref[lo] - pref[L] >= l) hi = lo;
            if(pref[hi] - pref[L] >= l && pref[hi] - pref[L] <= u){
                  for(int j = i; j <= hi; j ++)
                        ans.push_back(vec[j].second);
                  sort(ans.begin(), ans.end());
                  break;
            }
      }

      return ans;
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:15:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < w.size(); i ++){
                      ~~^~~~~~~~~~
molecules.cpp:21:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < vec.size(); i ++){
                      ~~^~~~~~~~~~~~
molecules.cpp:28:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < vec.size(); i ++){
                      ~~^~~~~~~~~~~~

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