Submission #650714

#TimeUsernameProblemLanguageResultExecution timeMemory
650714Markomafko972Detecting Molecules (IOI16_molecules)C++14
0 / 100
1 ms468 KiB
#include "molecules.h" #include <bits/stdc++.h> #define X first #define Y second #define pb push_back #define pii pair<int, int> typedef long long ll; using namespace std; const int MOD = 1e9 + 7; const ll INF = 1e18; const int OFF = (1 << 20); ll pref[200005]; pair<int, int> p[200005]; vector<int> ispis(int poc, int kr) { vector<int> sol; for (int i = poc; i <= kr; i++) { sol.push_back(p[i].Y); } return sol; } vector<int> find_subset(int l, int u, vector<int> w) { reverse(w.begin(), w.end()); w.push_back(0); reverse(w.begin(), w.end()); for (int i = 0; i < w.size(); i++) { p[i] = {w[i], i-1}; } sort(p, p + (int)w.size()); int n = (int)w.size()-1; for (int i = 1; i < (int)w.size(); i++) { pref[i] = pref[i-1] + p[i].X; } for (int i = 1; i <= n; i++) { ll d = pref[i]; ll g = pref[n] - pref[n-i]; if (d >= l && d <= u) return ispis(1, i); if (g >= l && g <= u) return ispis(n-i+1, n); if (d < l && g > u) { for (int j = i+1; j <= n; j++) { d = d + p[j].X - p[j-i].X; if (d >= l && d <= u) return ispis(j-i+1, j); } } } assert(0); return {}; }

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for (int i = 0; i < w.size(); 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...