| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 61364 | 2018-07-25T16:28:00 Z | nvmdava | Detecting Molecules (IOI16_molecules) | C++17 | 0 ms | 0 KB |
#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
struct mol{
int loc, val;
bool operator<(const mol& rhs) const{
return val <= rhs.val;
}
};
vector<mol> v;
vector<int> s;
std::vector<int> find_subset(int l, int u, std::vector<int> w) {
int i, n = w.size();
mol tmp;
for( i = 0; i < n; i++){
tmp.loc = i;
tmp.val = w[i];
v.push_back(tmp);
}
sort(v.begin(), v.end());
s.push_back(0);
for(i = 0; i < n; i++){
s.push_back(s[i] + v[i].val);
}
for( i = 1;i <=n ; i++){
if(s[i ] > u){
break;
}
if(s[n] - s[ n - i] >= l){
break;
}
}
if(s[i] > u || i == n + 1){
return std::vector<int>(0);
}
vector<int> ans;
int j;
/*if(n == i){
for(i = i - 1; i >= 0 ; i--){
ans.push_back(v[i].loc);
}
return ans;
}
for( j = 1; n - j - i >=0 ;j++){
if(n - j == i){
for(i = i - 1; i >= 0 ; i--){
ans.push_back(v[i].loc);
}
break;
}
if(s[n - j] - s[n - i -j] < l){
ans.push_back(v[n - j].loc);
l -= v[n - j].val;
i--;
if(i == 0){
break;
}
}
}*/
j = n - 1;
while(i--){
if(j + 1= i){
for(j = 0; j < i;j++){
ans.push_back(v[j].loc);
}
break;
}
while(s[j] - s[j - i] >= l){
j--;
}
ans.push_back(v[j].loc);
l -= v[j].val;
j--;
}
return ans;
}