제출 #366183

#제출 시각아이디문제언어결과실행 시간메모리
366183iliccmarkoDetecting Molecules (IOI16_molecules)C++14
19 / 100
1 ms512 KiB
#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 -= (ll)a[ind].first; s.insert(pq.top()); pq.pop(); sum += (ll)(a[i].first); pq.push(a[i]); s.erase(a[i]); while(true) { ll raz = (ll)u - sum; auto x = make_pair((int)raz, -1); auto xx = lower_bound(all(s), x); if(xx!=s.begin()) { xx--; pq.push(make_pair(xx->first, xx->second)); sum += xx->first; s.erase(xx); } else break; } if(sum<=u&&sum>=l) { while(len(pq)) { res.pb(pq.top().second); pq.pop(); } return res; } } while(len(res)) res.pop_back(); return res; }
#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...