Submission #1050539

#TimeUsernameProblemLanguageResultExecution timeMemory
1050539EntityPlanttDetecting Molecules (IOI16_molecules)C++17
100 / 100
36 ms6348 KiB
#include "molecules.h" #include <algorithm> #include <array> using namespace std; vector <int> construct(vector <array <int, 2>> &w, int left, int right) { vector <int> ret(left + w.size() - right - 1); for (int i = 0; i < left; i++) ret[i] = w[i][1]; for (int i = 0; i < w.size() - right - 1; i++) ret[i + left] = w[i + right + 1][1]; return ret; } vector <int> find_subset(int l, int u, vector <int> _w) { vector <array <int, 2>> w; for (int i = 0; i < _w.size(); i++) w.push_back({_w[i], i}); long long sum = 0; int n = w.size(); sort(w.begin(), w.end()); int left = 0, right = n - 1; while (right >= 0 && sum < l) sum += w[right--][0]; if (sum < l) return {}; if (sum <= u) return construct(w, 0, right); while (sum < l || sum > u) { sum += w[left++][0]; if (left == n) return {}; while (right < n - 1 && sum > u) sum -= w[++right][0]; } return construct(w, left, right); }

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> construct(std::vector<std::array<int, 2> >&, int, int)':
molecules.cpp:8:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |  for (int i = 0; i < w.size() - right - 1; i++) ret[i + left] = w[i + right + 1][1];
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~
molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:13:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for (int i = 0; i < _w.size(); i++) w.push_back({_w[i], i});
      |                  ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...