제출 #425603

#제출 시각아이디문제언어결과실행 시간메모리
425603dreezyDetecting Molecules (IOI16_molecules)C++17
46 / 100
1084 ms10036 KiB
#include <bits/stdc++.h> #include "molecules.h" using namespace std; #define pb push_back #define pi pair<int,int> #define ll long long #define mp make_pair vector<int> find_subset(int l, int u, vector<int> ww) { int n = ww.size(); vector<ll> w(n); pi sorted[n]; for(int i =0; i<n ;i++){ w[i] = ww[i]; sorted[i] = {ww[i], i}; } sort(sorted, sorted + n); int start = lower_bound(sorted, sorted + n, mp(u + 1, -1)) - sorted; start--; set<pair<int, pair<int,int>>> pos;//val, w, ind vector<bool> nums(1e5 + 5); int num_ans = -1; vector<int> ans; vector<ll> presum(n); presum[0] = sorted[0].first; for(int s = 1; s <= start; s++){ presum[s] = presum[s-1] + sorted[s].first; //cout << s<<": "<<presum[s]<<endl; } for(; start >=0; start--){ int i = sorted[start].second; //if( cursum + weights[i].w > u) continue; if(w[i] >=l && w[i] <= u){ return vector<int>(1, i); } set<int> ins; bool won = false; for(pair<int,pair<int,int>> val : pos){ int num = val.first; if(num + w[i] >= l && num+w[i] <= u){ num_ans = num; ans.pb(i); won = true; break; } if(num + w[i] < l ){ ins.insert(num+w[i]); } } if(won ) break; if(presum[start] + w[i] >= l and !nums[w[i]]){ pos.insert({w[i], {w[i], i}}); nums[w[i]] = true; } for(int val : ins){ if(presum[start] + val >= l and !nums[val]){ pos.insert({val, {w[i], i}}); nums[val] = true; } } } if(num_ans == -1) return vector<int>(); while(num_ans != 0){ pair<int, pi> val = *lower_bound(pos.begin(), pos.end(), mp(num_ans, mp(-1, -1))); ans.pb(val.second.second); num_ans = num_ans - val.second.first; } sort(ans.begin(), ans.end()); return ans; } /***************/
#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...