2018年5月23日 星期三

(IOI) 2009 Day 2 p4 Salesman

https://contest.yandex.com/ioi/contest/1363/problems/H/

這題有個關鍵(?) : 所有的位置 (展覽 + 家) 都不一樣。

所以,先考慮 60 pts (沒有兩個展覽在同一天),這個可以用DP去實現。

dp[i] --> 在位置 i 當作最後一個 展覽,最佳的獲利是多少。

這樣一來, dp[i] = max( dp[j] + cost(i,j) ) , 其中 cost (i,j) 是 位置 i  到位置 j 的距離。

因為距離的cost有兩種:一種是 用 U 的,一種是用 D 的,所以要開兩個線段樹分別存下來(?

這樣,就可以在 O(N lg N) 的複雜度解決這題。

接下來,考慮 有多個展覽在同一天。

可以發現,對於最佳解,有一個固定的pattern是:先走到某一個展覽,在一直延那個展覽往右 / 往左走。

於是,好好地用上面那個線段樹搞一搞,就okay惹~

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;
#define F first
#define S second

#define SZ(x) ((int)(x).size())

pii operator+(const pii &p1,const pii &p2)
{
    return make_pair(max(p1.F,p2.F),max(p1.S,p2.S));
}

const int INF = 2000000009;
const int POS_MAX = 500004;
const int POS_MIN = -1;

pii ee = make_pair(-INF,-INF);

struct Node
{
    Node *lc,*rc;
    pii val;
    Node():lc(NULL),rc(NULL),val(ee){}
    void pull()
    {
        val = (lc->val + rc->val);
    }
};

Node* Build(int L,int R)
{
    Node* node = new Node();
    if (L==R)
    {
        return node;
    }
    int mid=(L+R)>>1;
    node->lc = Build(L,mid);
    node->rc = Build(mid+1,R);
    return node;
}

void modify(Node* node,int L,int R,int pos,pii val)
{
    if (L == R)
    {
        node->val = val;
        return;
    }
    int mid=(L+R)>>1;
    if (pos <= mid) modify(node->lc,L,mid,pos,val);
    else modify(node->rc,mid+1,R,pos,val);
    node->pull();
}

pii query(Node* node,int L,int R,int l,int r)
{
    if (l>R || L>r) return ee;
    else if (l<=L && R<=r) return node->val;
    int mid=(L+R)>>1;
    return (query(node->lc,L,mid,l,r) + query(node->rc,mid+1,R,l,r));
}

int dp[POS_MAX];

int t[POS_MAX],l[POS_MAX],m[POS_MAX];

vector<int> tt[POS_MAX];

int main ()
{
    int n,u,d,s;
    scanf("%d %d %d %d",&n,&u,&d,&s);
    ++s;
    int nn = 500003;
    Node* root = Build(1,nn);
    for (int i=1;n>=i;i++)
    {
        scanf("%d %d %d",&t[i],&l[i],&m[i]);
        ++l[i];
        tt[ t[i] ].push_back(i);
    }
    //swap(d,u);
    modify(root,1,nn,s, make_pair( dp[s]-(s-POS_MIN)*u , dp[s]-(POS_MAX-s)*d ) );
    for (int ii=1;nn>=ii;ii++)
    {
        //if (SZ(tt[ii]) != 1) continue;
        //cout << "ii = " << ii << endl;
        if (SZ(tt[ii]) >= 1)
        {
            for (int i:tt[ii])
            {
                pii p = query(root,1,nn,1,l[i]-1);
                pii q = query(root,1,nn,l[i]+1,nn);
                int mx = -INF;
                if (p.S != -INF)
                {
                    mx = max(mx,p.S + (POS_MAX-l[i])*d);
                }
                if (q.F != -INF)
                {
                    mx = max(mx,q.F + (l[i]-POS_MIN)*u);
                }
                dp[ l[i] ] = mx + m[i];
                //cout << "dp [ " << l[i] << " ] = " << dp[ l[i] ] << endl;
                //modify(root,1,nn,l[i], make_pair( dp[ l[i] ]-( l[i] -POS_MIN)*u , dp[ l[i] ]-(POS_MAX- l[i] )*d ) );
            }
            for (int i:tt[ii])
            {
                modify(root,1,nn,l[i], make_pair( dp[ l[i] ]-( l[i] -POS_MIN)*u , dp[ l[i] ]-(POS_MAX- l[i] )*d ) );
            }
        }
        if (SZ(tt[ii]) > 1)
        {
            sort(tt[ii].begin(),tt[ii].end(),[](const int &a,const int &b)
             {
                 return l[a] < l[b];
             });
            //starting from l --> r
            pii ptmp = query(root,1,nn,1,l[ tt[ii][0] ]-1);
            int lmax = ptmp.S;
            for (int iii=0;SZ(tt[ii])>iii;iii++)
            {
                int i = tt[ii][iii];
                dp[ l[i] ] = max( dp[ l[i] ], lmax + (POS_MAX - l[i])*d + m[i] );
                lmax += m[i];
                if (iii == SZ(tt[ii]) - 1) break;
                int nxti = tt[ii][iii+1];
                pii qtmp = query(root,1,nn,l[i],l[nxti]-1);
                lmax = max(lmax,qtmp.S);
            }
            //starting from r --> l
            reverse(tt[ii].begin(),tt[ii].end());
            ptmp = query(root,1,nn,l[ tt[ii][0] ]+1,nn);
            int rmax = ptmp.F;
            for (int iii=0;SZ(tt[ii])>iii;iii++)
            {
                int i = tt[ii][iii];
                dp[ l[i] ] = max( dp[ l[i] ], rmax + (l[i] - POS_MIN)*u + m[i]);
                rmax += m[i];
                if (iii == SZ(tt[ii]) - 1) break;
                int nxti = tt[ii][iii+1];
                pii qtmp = query(root,1,nn,l[nxti]+1,l[i]);
                rmax = max(rmax,qtmp.F);
            }
            /*reverse(tt[ii].begin(),tt[ii].end());
            for (int iii=1;SZ(tt[ii])>iii;iii++)
            {
                int i = tt[ii][iii];
                int prei = tt[ii][iii-1];
                dp[i] = max(dp[i],dp[prei] + (l[i] - l[prei])*d);
            }
            reverse(tt[ii].begin(),tt[ii].end());
            for (int iii=1;SZ(tt[ii])>iii;iii++)
            {
                int i = tt[ii][iii];
                int prei = tt[ii][iii-1];
                dp[i] = max(dp[i],dp[prei] + (l[prei] - l[i])*u);
            }*/
            for (int i:tt[ii])
            {
                modify(root,1,nn,l[i], make_pair( dp[ l[i] ]-( l[i] -POS_MIN)*u , dp[ l[i] ]-(POS_MAX- l[i] )*d ) );
            }
        }
    }
    //swap(d,u);
    int ans = 0;
    for (int i=1;POS_MAX>i;i++)
    {
        /*if (dp[i])
        {
            cout << "i = " << i << " , dp = " <<dp[i] << endl;
        }*/
        if (i < s)
        {
            ans = max(ans,dp[i] - (s-i)*d);
        }
        else
        {
            ans = max(ans,dp[i] - (i-s)*u);
        }
    }
    printf("%d\n",ans);
}

(IOI) 2009 Day 2 p3 Regions

https://contest.yandex.com/ioi/contest/1363/problems/G/

首先,可以先把長官關係轉化成一顆樹,並且給定尤拉序列(Euler tour)。

所以,接下來詢問就變成:有多少區間pair(x,y),使得區間 x 屬於 r1,區間 y屬於 r2,並且r1完整包覆r2。

到這邊,可以先提出很多種算法,到時候再一起併起來之類的(?)

 定義 S1 是 r1 集合的大小, S2 是 r2集合的大小

(1) 預處理答案

預處理所有的 (r1,r2) 組合,注意到對於一個r1,可以在O(N)的時間 (走訪這棵樹) 求出所有 r2的答案。

(2)  O(S1 + S2)

如果 r1 和 r2 是已經排好序的話,就可以好好的使用類似雙指針 (類似而已,實作細節可參考底下的query3() )。

(3) O(S1 log S2) or O(S2 log S1)

好好的寫XD。

對於每個 r ,先按照尤拉序列走訪後的區間排序,之後開個持久化線段樹,好好的想辦法讓每次的問題都做到 log 的查詢時間

這樣一來,有兩種併法:

(一)

(1) + (2)
如果 S1, S2 其中一個 > C,使用 (1),否則使用(2)
取C = N^0.5的話,分析複雜度後會是好的。

(二)

(2) + (3)  //下面code的寫法

如果S1, S2其中一個 > C,使用(3) ,選擇複雜度比較小的那個
否則使用 (2)

適當的取C,會是好的XDDD。

#include <bits/stdc++.h>
using namespace std;

struct Node
{
    Node *lc,*rc;
    int sum;
    Node():lc(NULL),rc(NULL),sum(0){}
    void pull()
    {
        sum = lc->sum + rc->sum;
    }
};

Node* Build(int L,int R)
{
    Node* node = new Node();
    if (L==R) return node;
    int mid=(L+R)>>1;
    node->lc = Build(L,mid);
    node->rc = Build(mid+1,R);
    return node;
}

Node* getNode(Node* old)
{
    Node* node = new Node();
    node->lc = old->lc;
    node->rc = old->rc;
    node->sum = old->sum;
    return node;
}

void modify(Node* old,Node* node,int L,int R,int pos,int val)
{
    if (L==R)
    {
        node->sum += val;
        return;
    }
    int mid=(L+R)>>1;
    if (pos <= mid)
    {
        node->lc = getNode(old->lc);
        modify(old->lc,node->lc,L,mid,pos,val);
    }
    else
    {
        node->rc = getNode(old->rc);
        modify(old->rc,node->rc,mid+1,R,pos,val);
    }
    node->pull();
}

int query(Node* node,int L,int R,int l,int r)
{
    if (l>R || L>r) return 0;
    else if (l<=L && R<=r) return node->sum;
    int mid=(L+R)>>1;
    return query(node->lc,L,mid,l,r) + query(node->rc,mid+1,R,l,r);
}

typedef pair<int,int> pii;
const int N = 200006;

#define SZ(x) ((int)(x).size())

vector<int> G[N];
vector<pii> rr[N];
int r_pos[N];



#define F first
#define S second

pii p[N];

int stamp;

void dfs(int now)
{
    p[now].F = (++stamp);
    for (int i:G[now])
    {
        dfs(i);
    }
    p[now].S = stamp;
}

Node* root[N];
int pre[N];

int n;

int query1(int x,int y)
{
    //how many interval cover y
    //size of y is smaller
    int ret=0;
    int lastpos = 0;
    for (pii p:rr[y])
    {
        int pos = lower_bound(rr[x].begin() + lastpos,rr[x].end(),p) - rr[x].begin();
        lastpos = pos;
        if (pos)
        {
            ret += query(root[ pre[x]+pos ],1,n,p.S,n);
        }
    }
    return ret;
}

int query2(int x,int y)
{
    //how many interval within y
    //size of y is smaller
    //cout << "X = " << x << " , y = " <<y <<endl;
    int ret=0;
    int lastpos=0;
    for (pii p:rr[y])
    {
        int pos = lower_bound(rr[x].begin()+lastpos,rr[x].end(),p) - rr[x].begin();
        //cout << " p = " << p.F <<" , " << p.S << " , pos = " << pos << endl;
        lastpos = pos;
        if (pos != 0)
        {
            //cout << "pos = " << pos << " , pre[x] = " << pre[x] << " , pre[x+1] = " << pre[x+1] <<endl;
            ret += (query(root[ pre[x+1] ],1,n,p.F,p.S) - query(root[ pre[x]+pos ],1,n,p.F,p.S));
        }
        else
        {
            ret += query(root[ pre[x+1] ],1,n,p.F,p.S);
        }
    }
    return ret;
}

int query3(int x,int y)
{
    int ptrl = 0;
    int ptrr = -1;
    int ret=0;
    for (int i=0;SZ(rr[x])>i;i++)
    {
        while (ptrl != SZ(rr[y]) && rr[y][ptrl].F < rr[x][i].F) ++ptrl;
        while (ptrr != -1 && rr[y][ptrr].F > rr[x][i].S) --ptrr;
        while (ptrr != SZ(rr[y])-1 && rr[y][ptrr+1].F <= rr[x][i].S) ++ptrr;
        ret += (ptrr - ptrl + 1);
    }
    return ret;
}

const int C = 706;

int main ()
{
    int r,q;
    scanf("%d%d%d",&n,&r,&q);
    for (int i=1;n>=i;i++)
    {
        if (i == 1)
        {
            int x;
            scanf("%d",&x);
            //rr[x].push_back(i);
            r_pos[i] = x;
            continue;
        }
        int par,x;
        scanf("%d%d",&par,&x);
        G[par].push_back(i);
        //rr[x].push_back(i);
        r_pos[i] = x;
    }
    dfs(1);
    for (int i=1;n>=i;i++)
    {
        //cout << "i = " <<i << " , r_pos = " << r_pos[i] << " , p = " << p[i].F << " , " << p[i].S << endl;
        rr[ r_pos[i] ].push_back(p[i]);
    }
    for (int i=1;r>=i;i++)
    {
        sort(rr[i].begin(),rr[i].end());
        pre[i+1] = pre[i] + SZ(rr[i]);
        //cout << "i = " <<i << " , pre = " << pre[i] <<endl;
    }
    int id=1;
    root[0] = Build(1,n);
    for (int i=1;r>=i;i++)
    {
        if (SZ(rr[i]) == 0) continue;
        root[id] = getNode(root[0]);
        modify(root[0],root[id],1,n,rr[i][0].S,1);
        ++id;
        //cout << "hi1" <<endl;
        for (int j=1;SZ(rr[i])>j;j++)
        {
            //cout << "jj = " << j << endl;
            root[id] = getNode(root[id-1]);
            modify(root[id-1],root[id],1,n,rr[i][j].S,1);
            ++id;
        }
        //cout << "i = " << i <<" , id = " << id << endl;
    }
    map<pii,int> mp;
    while (q--)
    {
        int r1,r2;
        scanf("%d%d",&r1,&r2);
        if (SZ(rr[r1]) == 0 ||SZ(rr[r2]) == 0)
        {
            printf("0\n");
            fflush(stdout);
            continue;
        }
        if (mp.find(make_pair(r1,r2)) != mp.end())
        {
            printf("%d\n",mp[ make_pair(r1,r2) ]);
            fflush(stdout);
            continue;
        }
        int ans = 0;
        if (SZ(rr[r1]) < C && SZ(rr[r2]) < C)
        {
            ans = query3(r1,r2);
        }
        else if (SZ(rr[r1]) >= SZ(rr[r2]))
        {
            ans = query1(r1,r2);
        }
        else
        {
            ans = query2(r2,r1);
        }
        mp[ make_pair(r1,r2) ] = ans;
        printf("%d\n",ans);
        fflush(stdout);
    }
}


(IOI) 2009 Day 2 p2 Mecho

https://contest.yandex.com/ioi/contest/1363/problems/F/

BFS + 二分搜答案

注意到二分搜的範圍要夠大喔 (可以想想極端case XD,被這個卡超久的)

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;

#define F first
#define S second

int mp[806][806];
int bee_dis[806][806];

int dx[4] = {1,0,-1,0} , dy[4] = {0,1,0,-1};

int n,s;
pii st;
pii ed;

int dis[806][806];

bool can(int mid)
{
    queue<pii> que;
    memset(dis,-1,sizeof(dis));
    assert(st != make_pair(0,0));
    if (bee_dis[st.F][st.S] == -1) assert(0);
    if (bee_dis[st.F][st.S] <= mid) return false;
    dis[st.F][st.S] = 0;
    que.push(st);
    while (!que.empty())
    {
        pii p=que.front();
        que.pop();
        //cout << "p = " << p.F << " , " << p.S<<
        for (int i=0;4>i;i++)
        {
            int tx=p.F+dx[i];
            int ty=p.S+dy[i];
            if (make_pair(tx,ty) == ed) return true;
            if (mp[tx][ty] == 0 || dis[tx][ty] != -1) continue;
            if (bee_dis[tx][ty] == -1)
            {
                dis[tx][ty] = dis[p.F][p.S] + 1;
                que.push(make_pair(tx,ty));
            }
            else
            {
                int want_dis = dis[p.F][p.S] + 1;
                int del = 0;
                if (want_dis % s == 0)
                {
                    del = 0;
                }
                if (want_dis/s + del + mid < bee_dis[tx][ty])
                {
                    dis[tx][ty] = want_dis;
                    que.push(make_pair(tx,ty));
                }
            }
        }
    }
    return false;
}

int main ()
{
    cin >> n >> s;
    vector<pii> bees;
    for (int i=1;n>=i;i++)
    {
        string ss;
        cin >>ss;
        for (int j=1;n>=j;j++)
        {
            char c = ss[j-1];
            if (c == 'T') continue;
            if (c == 'G')
            {
                mp[i][j] = 1;
            }
            else if (c == 'M')
            {
                st = make_pair(i,j);
                mp[i][j] = 1;
            }
            else if (c == 'D')
            {
                ed = make_pair(i,j);
                mp[i][j] = 2;
            }
            else if (c == 'H')
            {
                bees.push_back(make_pair(i,j));
                mp[i][j] = 1;
            }
        }
    }
    memset(bee_dis,-1,sizeof(bee_dis));
    queue<pii> que;
    for (pii p:bees)
    {
        que.push(p);
        bee_dis[p.F][p.S] = 0;
    }
    while (!que.empty())
    {
        pii p=que.front();
        que.pop();
        for (int i=0;4>i;i++)
        {
            int tx=p.F+dx[i];
            int ty=p.S+dy[i];
            if (mp[tx][ty] == 1 && bee_dis[tx][ty] == -1)
            {
                que.push(make_pair(tx,ty));
                bee_dis[tx][ty] = bee_dis[p.F][p.S] +1;
            }
        }
    }
    if (!can(0))
    {
        cout << -1 << endl;
        return 0;
    }
    int L=0,R = 650212;
    while (R-L != 1)
    {
        int mid=(L+R)>>1;
        if (can(mid)) L = mid;
        else R = mid;
    }
    //assert(L != 20005);
    //assert(can(L) && !can(L+1));
    cout <<L << endl;
}

(IOI) 2009 Day 2 p1 Garage

https://contest.yandex.com/ioi/contest/1363/problems/E/

implementation task (?

#include <bits/stdc++.h>
using namespace std;

const int N = 5006;

int r[N];
int w[N];

int hhave[N];

int main ()
{
    int n,m;
    scanf("%d %d",&n,&m);
    //n --> parking space
    //m --> cars
    for (int i=1;n>=i;i++)
    {
        scanf("%d",&r[i]);
    }
    for (int i=1;m>=i;i++)
    {
        scanf("%d",&w[i]);
    }
    int ans=0;
    deque<int> wait;
    for (int i=1;2*m>=i;i++)
    {
        int x;
        scanf("%d",&x);
        if (x>0)
        {
            bool found = false;
            for (int j=1;n>=j;j++)
            {
                if (hhave[j] == 0)
                {
                    ans += r[j] * w[x];
                    hhave[j] = x;
                    found = true;
                    break;
                }
            }
            if (!found)
            {
                wait.push_back(x);
            }
        }
        else if (x < 0)
        {
            x = -x;
            for (int i=1;n>=i;i++)
            {
                if (hhave[i] == x)
                {
                    hhave[i] = 0;
                    if (!wait.empty())
                    {
                        hhave[i] = wait[0];
                        ans += w[ wait[0] ] * r[i];
                        wait.pop_front();
                    }
                }
            }
        }
    }
    printf("%d\n",ans);
}

(IOI) 2009 Day 1 p4 Raisins

https://contest.yandex.com/ioi/contest/1362/problems/D/

先做二維前綴和之後好好DP即可。

#include <bits/stdc++.h>
using namespace std;

const int N = 51;

int a[N][N];
int pre[N][N];
int dp[N][N][N][N];

int cal(int x1,int y1,int x2,int y2)
{
    return pre[x2][y2] - pre[x2][y1-1] - pre[x1-1][y2] + pre[x1-1][y1-1];
}

int solve(int x1,int y1,int x2,int y2)
{
    if (x1 == x2 && y1 == y2) return 0;
    if (dp[x1][y1][x2][y2] != -1) return dp[x1][y1][x2][y2];
    int &ret = dp[x1][y1][x2][y2];
    ret = 2147483647;
    int _ = cal(x1,y1,x2,y2);
    for (int i=x1;x2>i;i++)
    {
        ret = min(ret,_ + solve(x1,y1,i,y2) + solve(i+1,y1,x2,y2));
    }
    for (int j=y1;y2>j;j++)
    {
        ret = min(ret,_ + solve(x1,y1,x2,j) + solve(x1,j+1,x2,y2));
    }
    //cout << "x1 = " <<x1 << " , y1 = " <<y1 << " , x2 = " << x2 << " , y2 = " << y2 << " , ret = " << ret <<endl;
    return ret;
}

int main ()
{
    memset(dp,-1,sizeof(dp));
    int n,m;
    scanf("%d %d",&n,&m);
    for (int i=1;n>=i;i++)
    {
        for (int j=1;m>=j;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    for (int i=1;n>=i;i++)
    {
        for (int j=1;m>=j;j++)
        {
            pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j];
        }
    }
    printf("%d\n",solve(1,1,n,m));
}

(IOI) 2009 Day 1 p3 POI

https://contest.yandex.com/ioi/contest/1362/problems/C/

implementation task (?

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;

bool adj[2002][2002];

int score[2002];

int main()
{
    int n,t,p,x;
    scanf("%d %d %d",&n,&t,&p);
    for (int i=1;t>=i;i++)
    {
        score[i] = n;
    }
    for (int i=1;n>=i;i++)
    {
        for (int j=1;t>=j;j++)
        {
            scanf("%d",&x);
            adj[i][j] = x;
            score[j] -= adj[i][j];
        }
    }
    vector< pair<pii,int> > v;
    for (int i=1;n>=i;i++)
    {
        int tot=0;
        int cnt=0;
        for (int j=1;t>=j;j++)
        {
            tot += adj[i][j] * score[j];
            cnt += adj[i][j];
        }
        v.push_back(make_pair(make_pair(-tot,-cnt),i));
        if (i == p)printf("%d ",tot);
    }
    sort(v.begin(),v.end());
    for (int i=1;n>=i;i++)
    {
        if (v[i-1].second == p)
        {
            printf("%d\n",i);
            return 0;
        }
    }
}

(IOI) 2009 Day 1 p2 Hiring

https://contest.yandex.com/ioi/contest/1362/problems/B/

可以先用二分搜來確認人數。

人數確認好了後,可以好好的利用比例的關係(?)去做比較,就可以找出最小值的答案這樣。


#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<LL,LL> pii;
const int N = 500006;

#define F first
#define S second

pii p[N];
int v[N];
int n;
LL w;

vector<int> vv;

bool doo(int mid,bool get_ans = false)
{
    priority_queue<pii> pq;
    LL tot=0;
    for (int i=1;mid-1>=i;i++)
    {
        pq.push(make_pair(p[ v[i] ].S , v[i]) );
        tot += p[ v[i] ].S;
    }
    bool ret = false;
    pii ww = make_pair(w,1);
    int ii = -1;
    for (int i=mid;n>=i;i++)
    {
        if (p[ v[i] ].F * (tot + p[ v[i] ].S) * ww.S <= p[ v[i] ].S*ww.F)
        {
            ret = true;
            ii = i;
            ww = make_pair(p[ v[i] ].F * (tot + p[ v[i] ].S) , p[ v[i] ].S);
        }
        if (mid != 1 && p[ v[i] ].S < pq.top().F)
        {
            tot -= pq.top().F;
            pq.pop();
            pq.push(make_pair(p[ v[i] ].S,v[i]));
            tot += p[ v[i] ].S;
        }
    }
    if (get_ans)
    {
        while (!pq.empty()) pq.pop();
        tot=0;
        for (int i=1;mid-1>=i;i++)
        {
            pq.push(make_pair(p[ v[i] ].S , v[i]) );
            tot += p[ v[i] ].S;
        }
        for (int i=mid;n>=i;i++)
        {
            if (i == ii)
            {
                ret = true;
                vv.push_back(v[i]);
                while (!pq.empty())
                {
                    pii p=pq.top();
                    vv.push_back(p.S);
                    pq.pop();
                }
                return true;
            }
            if (mid != 1 && p[ v[i] ].S < pq.top().F)
            {
                tot -= pq.top().F;
                pq.pop();
                pq.push(make_pair(p[ v[i] ].S,v[i]));
                tot += p[ v[i] ].S;
            }
        }
    }
    return ret;
}

int main ()
{
    scanf("%d %lld",&n,&w);
    for (int i=1;n>=i;i++)
    {
        v[i] = i;
        scanf("%lld %lld",&p[i].F,&p[i].S);
    }
    sort(v+1,v+n+1,[&](const int &a,const int &b)
     {
         return p[a].F*p[b].S < p[a].S*p[b].F;
     })
    ;
    int L=0,R=n+1;
    //L is the answer
    while (R-L != 1)
    {
        int mid=(L+R)>>1;
        if (doo(mid)) L = mid;
        else R = mid;
    }
    printf("%d\n",L);
    doo(L,true);
    for (int i:vv) printf("%d\n",i);
}