제출 #425867

#제출 시각아이디문제언어결과실행 시간메모리
425867ivan24Detecting Molecules (IOI16_molecules)C++14
0 / 100
1 ms204 KiB
#include <bits/stdc++.h> #include "molecules.h" using namespace std; using ll = long long int; typedef vector<ll> vi; typedef vector<vi> vvi; typedef pair<ll,ll> ii; typedef vector<ii> vii; typedef vector<vii> vvii; struct val{ ll w,idx; val(){} val (ll w, ll idx): w(w),idx(idx){ } bool operator>(const val& rhs) const { if (w == rhs.w) return idx > rhs.idx; return (w > rhs.w); } bool operator<(const val& rhs) const { if (w == rhs.w) return idx < rhs.idx; return (w < rhs.w); } void print(){ cout << "w: " << w << " " << "idx: " << idx << endl; } }; std::vector<int> find_subset(int l, int u, std::vector<int> w) { vi prefSum; vector<val> vals; ll n = w.size(); vals.resize(n); for (ll i = 0; n > i; i++){ vals[i] = val(w[i],i); } sort(vals.begin(),vals.end()); reverse(vals.begin(),vals.end()); prefSum.assign(n+1,0); for (ll i = 0; n > i; i++){ prefSum[i+1] = prefSum[i]; prefSum[i+1] += vals[i].w; } ll ptr = n; for (ll i = 0; n >= i; i++){ if (u >= prefSum[i] && prefSum[i] >= l){ vector<int> v; for (ll j = 0; i > j; j++) v.push_back(vals[j].idx+1); return v; }else if (prefSum[i] > u){ ptr = min(ptr,i); } } long long int curSum = prefSum[ptr]; for (ll i = ptr; n > i; i++){ curSum += vals[i].w; curSum -= vals[i-ptr].w; if (u >= curSum && curSum >= l){ vector<int> v; for (ll j = i; j > i-ptr; j--)v.push_back(vals[j].idx+1); return v; } } return 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...