Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <cstdio>
- #define foreach(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++i)
- using namespace std;
- typedef long long int64;
- const double eps = 1e-9;
- struct item{
- int q, index;
- int64 sum;
- item *l, *r;
- item(){}
- };
- typedef item* pnode;
- bool cm = 0;
- item _[1000001];
- int64 ln = 0;
- pnode node(int64 q, int64 index){
- pnode res = &_[ln++];
- res->q = q, res->index = index, res->sum = q;
- res->l = res->r = 0;
- return res;
- }
- #define sum(x) ((x) ? ((x)->sum) : 0)
- #define upd_sum(x) ((x)->sum = sum((x)->l) + sum((x)->r) + (x)->q)
- static int cc = 0;
- pnode merge(pnode l, pnode r){
- if (!l || !r)
- return l ? l : r;
- if (l->q < r->q)
- swap(l, r);
- if (cc ^= 1)
- swap(l->l, l->r);
- l->r = merge(l->r, r);
- upd_sum(l);
- return l;
- }
- const int cmax = 500001;
- int n;
- int s[cmax], q[cmax];
- double sq[cmax];
- int64 w;
- int p[cmax];
- inline bool cmp(int a, int b){
- return sq[a] < sq[b];
- }
- pnode rt = 0;
- void print(pnode a, vector<int> &ans){
- if (!a)
- return;
- print(a->l, ans);
- ans.push_back(a->index + 1);
- print(a->r, ans);
- }
- int dl[cmax], len = 0;
- pnode where[cmax];
- vector<int> res;
- int sz = 0;
- #define init(x) ((x)->l = (x)->r = 0, (x)->sum = (x)->q)
- int main(){
- #ifdef CUTEBMAING
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- scanf("%d %lld", &n, &w);
- for (int i = 0; i < n; i++)
- scanf("%d %d", &s[i], &q[i]), sq[i] = 1.0 * s[i] / q[i];
- for (int i = 0; i < n; i++)
- p[i] = i;
- sort(p, p + n, cmp);
- int64 ans = 0, wh = 0;
- double cost = 0;
- for (int i = 0; i < n; i++)
- where[i] = node(q[i], i);
- for (int i = 0; i < n; i++){
- len = 0;
- dl[len++] = p[i];
- while (rt && 1.0 * sum(rt) * sq[p[i]] + eps > w)
- rt = merge(rt->l, rt->r), --sz;
- while (rt && 1.0 * sum(rt) * sq[p[i]] + s[p[i]] + eps > w){
- dl[len++] = rt->index;
- rt = merge(rt->l, rt->r), --sz;
- }
- double ccost = 1.0 * sum(rt) * sq[p[i]] + s[p[i]];
- if (ccost - eps < w && (ans < sz + 1 || (ans == sz + 1 && cost > ccost)))
- ans = sz + 1, wh = i, cost = ccost;
- for (int i = 0; i < len; i++)
- init(where[dl[i]]), rt = merge(rt, where[dl[i]]), ++sz;
- }
- rt = 0;
- for (int i = 0; i < wh; i++)
- init(where[p[i]]), rt = merge(rt, where[p[i]]);
- while (rt && 1.0 * sum(rt) * sq[p[wh]] + s[p[wh]] - eps > w)
- rt = merge(rt->l, rt->r);
- printf("%lld\n", ans);
- print(rt, res);
- if (ans > 0)
- res.push_back(p[wh] + 1);
- sort(res.begin(), res.end());
- foreach(i, res)
- printf("%d\n", *i);
- return 0;
- }
Add Comment
Please, Sign In to add comment