Submission #1031574

#TimeUsernameProblemLanguageResultExecution timeMemory
1031574pccDetecting Molecules (IOI16_molecules)C++17
100 / 100
62 ms14796 KiB
#include "molecules.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define fs first #define sc second std::vector<int> find_subset(int l, int u, std::vector<int> w) { int N = w.size(); vector<int> mx(N);iota(mx.begin(),mx.end(),0); sort(mx.begin(),mx.end(),[&](int a,int b){return w[a]>w[b];}); ll sum = 0; set<pii> chose; for(auto &now:mx){ if(l<=sum&&sum<=u){ vector<int> re; for(auto &i:chose)re.push_back(i.sc); return re; } if(sum<=u){ chose.insert(pii(w[now],now)); sum += w[now]; } } auto mn = mx; while(sum>u){ while(!mn.empty()&&chose.find(pii(w[mn.back()],mn.back())) != chose.end())mn.pop_back(); if(mn.empty())break; auto now = mn.back(); mn.pop_back(); auto out = *chose.rbegin(); sum -= out.fs; chose.erase(out); sum += w[now]; chose.insert(pii(w[now],now)); } vector<int> ans; for(auto &i:chose)ans.push_back(i.sc); return (sum<=u&&sum>=l?ans:vector<int>()); }
#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...