Submission #1098363

#TimeUsernameProblemLanguageResultExecution timeMemory
1098363dzhoz0Detecting Molecules (IOI16_molecules)C++17
69 / 100
2 ms856 KiB
#include "molecules.h" #include <bits/stdc++.h> using namespace std; vector<int> find_subset(int l, int u, vector<int> w) { int n = w.size(); vector<pair<int, int>> a(n); for(int i = 0; i < n; i++) { a[i].first = w[i]; a[i].second = i; } sort(a.begin(), a.end()); vector<int> ps(n); for(int i = 0; i < n; i++) { if(i == 0) ps[i] = a[i].first; else ps[i] = ps[i - 1] + a[i].first; } // for(int i = 0; i < n; i++) cout << a[i].first << ' '; cout << '\n'; // for(int i = 0; i < n; i++) cout << ps[i] << ' '; cout << '\n'; if(lower_bound(ps.begin(), ps.end(), l) != ps.end() && *lower_bound(ps.begin(), ps.end(), l) <= u) { vector<int> res; for(int i = 0; i < n; i++) { res.push_back(a[i].second); if(ps[i] >= l) return res; } } for(int i = 0; i < n - 1; i++) { auto it = lower_bound(ps.begin(), ps.end(), ps[i] + l); // cout << i << ' ' << *it - ps[i] << ' ' << u << '\n'; if(it != ps.end() && *it - ps[i] <= u) { vector<int> res; // cout << i << ' ' << it - ps.begin() << '\n'; for(int j = i + 1; j <= it - ps.begin(); j++) res.push_back(a[j].second); return res; } } return vector<int>(0); }
#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...