| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 366197 | iliccmarko | Detecting Molecules (IOI16_molecules) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define INF 1000000000
#define LINF 1000000000000000LL
#define pb push_back
#define all(x) x.begin(), x.end()
#define len(s) (int)s.size()
#define test_case { int t; cin>>t; while(t--)solve(); }
#define input(n, v) {for(int i = 0;i<n;i++) cin>>v[i];}
#define output(n, v) {for(int i = 0;i<n;i++) cout<<v[i]<<" "; cout<<endl;}
#define single_case solve();
#define line cout<<"------------"<<endl;
#define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); }
const int N = 2e5 + 5;
pair<int, int> a[N];
set<pair<int, int> > s;
vector<int> find_subset(int l, int u, vector<int> w)
{
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
vector<int> res;
int n = len(w);
for(int i = 0;i<n;i++)
{
a[i].first = w[i];
a[i].second = i;
}
sort(a, a+n);
ll sum = 0;
for(int i = 0;i<n;i++)
{
sum += (ll)a[i].first;
if(sum>(ll)u)
{
sum -= (ll)a[i].first;
break;
}
pq.push(a[i]);
if(sum<=u&&sum>=l)
{
while(len(pq))
{
auto x = pq.top();
res.pb(x.second);
pq.pop();
}
return res;
}
}
int vel = len(pq);
if(vel==n||!vel) return res;
for(int i = vel;i<n;i++)
{
s.insert(a[i]);
}
for(int i = vel;i<n;i++)
{
int ind = pq.top().second;
sum -= pq.top().first;
s.insert(pq.top());
pq.pop();
sum += (ll)(a[i].first);
pq.push(a[i]);
s.erase(a[i]);
ll raz = (ll)u - sum;
auto x = make_pair((int)raz, -1);
auto xx = s.upper_bound(all(s), x);
if(xx!=s.begin())
{
xx--;
pq.push(make_pair(xx->first, xx->second));
sum += xx->first;
s.erase(xx);
}
if(sum<=u&&sum>=l)
{
while(len(pq))
{
res.pb(pq.top().second);
pq.pop();
}
return res;
}
}
vector<int> ans;
return ans;
}