| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 206815 | 2020-03-05T13:33:11 Z | vardan__02 | Detecting Molecules (IOI16_molecules) | C++14 | 0 ms | 0 KB |
#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <set>
#include <map>
#include "molecules.h"
using namespace std;
typedef long long ll;
const long long N=200005;
#define MP make_pair
#define PB push_back
vector<int> find_subset(int l, int u, std::vector<int> w)
{
vector<ll> ans;
vector<pair<ll,ll> > a;
ll n = w.size();
for(ll i = 0; i < n; ++i)
a.PB(MP(w[i],i));
sort(a.begin(), a.end());
ll left = 0, right = 0, tiv = 0;
for(ll i = 0; i < n; ++i)
{
while(i < n && tiv < l)
{
tiv += a[i].first;
i++;
}
i--;
if(tiv < l)return ans;
if(tiv <= u)
{
if(u - l >= a[i].first - a[left].first)
{
for(ll j = left; j <= i; ++j)
ans.PB(a[j].second);
sort(ans.begin(), ans.end());
return ans;
}
else
{
while(left <= i && u - l < a[i].first - a[left].first)
{
tiv -= a[left].first;
left++;
}
right = i;
}
}
else
{
while(left <= i && tiv > u)
{
tiv -= a[left].first;
left++;
}
while(left <= i && u - l < a[i].first - a[left].first)
{
tiv -= a[left].first;
left++;
}
right = i;
}
}
tiv = 0;
for(ll i = left; i <= right; ++i)
tiv += a[i].first;
if(tiv >= l && tiv <= u && u - l >= a[right].first - a[left].first)
{
for(ll j = left; j <= right; ++j)
ans.PB(a[j].second);
sort(ans.begin(), ans.end());
return ans;
}
else
return ans;