I've solved this problem using set (so a bst). I've thought of a method of using a segment tree. How would you come about using a heap, I'm curious?

test it your self

after deleting this code, please
explain me why WA twoalias[animal]inbox[youknow]ru

#include <stdio.h>
#include <memory.h>


struct elt
{
    int c;
    short i;
};

elt T[100001];

int main()
{
    memset(T,0,sizeof(T));
    int N;
    scanf("%i",&N);
    short i;
    for (i=1;i<=N;i++)
    {
        int S,C;
        scanf("%i %i",&S,&C);
        if (C>T[S].c)
        {
            T[S].c=C;
            T[S].i=i;
        }
    }
    int j,ch=0;
    for (j=0;j<100001;j++) if (T[j].c>0) ch++;
    printf("%i\n",ch);
    for (j=0;j<100001;j++) if (T[j].c>0) printf("%i ",T[j].i);
    return 0;
}

Edited by author 29.08.2006 20:03

1. sort these orders for the following for loop;
2. can I serve current order? is there a not used day left for it? wow, that's easy if I can use std::set::upper_bound;
3. output our selected orders with delivery time.

// wow accepted, so lucky I am.

// after checked the discussion, found that this problem can be easily solve with priority queue, looks that priority queue is more convenient.

By my mind, my solution is right.
It builds a shedule of transporting with maximal money values superseding least values before that time.

But my solution falls on ninth test. I think that something wrong with that test.

Don't it mean he only deliver one whisky on one day?
I don't know the test while the others programmer offer...
Who can tell me what the problem mean?

The order is important for this test

e.g
on 1 test I answer
4
1 17
5 15
2 10
2 11
------------
3
4 2 1

It was good i don't have WA but on test 5 i have WA when i do something with my answers and they look like in example it passed WA5  and for this test answer must be:

4
1 4
1 2
2 5
2 2
---------
2
1 3


6
1 10
1 12
2 14
2 23
5 17
5 18
----------------------
4
4 3 6 5 <-- so its strange :) happy debuging
I have those answers and i have AC

Edited by author 18.03.2011 02:56

import java.util.Arrays;
import java.util.Scanner;

public class Timus1403 {

    /**
     * @param args
     */
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        Order[] order = new Order[n];
        int[] num = new int[100001];
        int[] ans = new int[100001];
        boolean[] used = new boolean[100001];
        Arrays.fill(used, false);
        for (int i = 0; i < order.length; i++) {
            int d = input.nextInt();
            int p = input.nextInt();
            order[i] = new Order(i + 1, d, p);
        }
        for (int i = 0; i < num.length; i++) {
            num[i] = i;
        }
        Arrays.sort(order);
        int count = 0;
        for (int i = 0; i < order.length; i++) {
            int j = order[i].deadline;
            if(num[j] > 0 && !used[num[j]]){
                count++;
                int x = num[j];
                ans[num[j]] = order[i].index;
                used[num[j]] = true;
                num[num[j]] = num[j] - 1;
                if(x == j){
                    continue;
                }
                num[order[i].deadline]--;

            }
        }
        System.out.println(count);
        for (int i = 0; i < used.length; i++) {
            if(used[i]){
                System.out.print(ans[i] + " ");
            }
        }


    }

}

class Order implements Comparable<Order>{
    public int index;
    public int deadline;
    public int price;

    public Order(int i, int d, int p){
        index = i;
        deadline = d;
        price = p;
    }

    @Override
    public String toString(){
        String ret = "";
        ret+= this.index + " " + this.deadline + " " + this.price;
        return ret;
    }

    public int compareTo(Order other) {
        return -(this.price - other.price);
    }

}

Edited by author 24.10.2010 08:20

Give me some hints please

import java.io.*;

class Courier{
    static PrintWriter p=new PrintWriter(System.out);
    static int f;
    static final int k=-'0';
    int mat[][],dp[],max;
    short N,a[],l[],sa,sl;
    boolean ok;

    static int nextInt() throws IOException{
        int t=0;
        for (f=System.in.read(); f<'0' || f>'9'; f=System.in.read());
        for (;f>='0' && f<='9'; t*=10,t+=f+k,f=System.in.read());
        return t;
    }

    Courier() throws IOException{
        N=(short)nextInt();
        mat=new int[N+1][3];
        short i=1;
        for (;i<=N; mat[i][0]=nextInt(),mat[i][1]=nextInt(),mat[i][2]=i++);
        a=new short[N];
        l=new short[N];
        dp=new int[N+1];
        qsort((short) 1,N);
        for (i=1;i<=N; i++){
            if (mat[i][0]>=1){
                a[sa++]=(short) mat[i][2];
                nadji(2,i,mat[i][1]);
                sa--;
            }
        }
        for (p.println(sl),i=0; i<sl; p.print(l[i++]),p.print(' '));
        p.flush();
    }

    void nadji(int k,short p, int s){
        if (k==N+1){
            if (s>max) for (sl=0,max=s; sl<sa; l[sl]=a[sl++]);
            ok=N==sl;
            return;
        }
        if (s<dp[k]) return;
        dp[k]=s;
        short i=(short) (p+1);
        for (;i<=N; i++){
            if (mat[i][0]>=k){
                a[sa++]=(short) mat[i][2];
                nadji(k+1,i,s+mat[i][1]);
                sa--;
                if (ok) return;
            }
        }
        if (s>max) for (max=s,sl=0; sl<sa; l[sl]=a[sl++]);
    }

    void qsort(short a, short b){
        short i=a,j=b,m=(short) ((i+j)>>1);
        int[] t;
        for (;i<j;){
            for (;mat[i][0]<mat[m][0] || (mat[i][0]==mat[m][0] && mat[i][1]<mat[m][1]); i++);
            for (;mat[m][0]<mat[j][0] || (mat[m][0]==mat[j][0] && mat[m][1]<mat[j][1]); j--);
            if (i<=j){
                if (i<j){
                    t=mat[i];
                    mat[i]=mat[j];
                    mat[j]=t;
                }
                i++;
                j--;
            }
        }
        if (i<b) qsort(i,b);
        if (a<j) qsort(a,j);
    }

}

public class Timus1403 {
    public static void main(String[] args) throws IOException{
        new Courier();
    }
}

Edited by author 07.08.2009 23:27

I have got wrong answer on first test!!
my program out right test on my computer!

The subject test data is too strange

I input:
6
1 10
1 12
2 14
2 23
5 17
5 18
output:
4
3 4 6 5  test is wa#15

I change algorithm ， input again

output
4
3 4 5 6    test is wa #9

but I think both the result are all right, why?



Edited by author 23.12.2008 05:33

Huh! Silly mistake! Be careful while counting numbers of deliveries!
Try such test:
5
1 5
3 14
6 4
8 1
9 7
While having WA5 I had answer:
5
0 0 0 0 2
and after:
5
1 2 3 4 5.

Edited by author 09.11.2007 02:33

Wrong answer on test #1

I tested my programm many times. I know, it works. Tell me please, why wrong answer? Maybe, it is input/output problem?

На 9ом тесте срок доставки больше, чем 100,000

What this is mean:

1584620    14:05:12
20 мар 2007 Pascal Accepted  0.001 176 КБ

1584617    14:02:35
20 мар 2007 1403 Time limit exceeded 11    0.015 156 КБ

1584609    14:00:01
20 мар 2007 1403 Time limit exceeded 2    0.001 156 КБ

1584603    13:56:00
20 мар 2007 1403 Time limit exceeded 20    0.001 176 КБ

1584602    13:55:09
20 мар 2007 1403 Time limit exceeded 3    0.001 156 КБ

Why 0.001 and TLE?

Could U give me Test2 please?
I can't find the errors of my program.

Could U give me Test2 please?
I can't find the errors of my program.