01204212/job queue

from 01204212

Job queue 1

You have n jobs to be executed in k servers, called server 0, server 1,..., and server k-1 (1 <= n <= 100,000; 1 <= k <= 100). These n jobs are job 0, job 1, job 2,..., job n-1. Each job i has to be processed by server s[i].

All jobs arrive to our system in order from job 0 to job n-1, and when it arrives it goes to the server that will process it. Each server processes jobs in the order that they arrive to the server. We assume that before the system starts processing any jobs, all jobs arrive at our system and are assigned to appropriate server queues.

The system works in synchronous rounds. Every server takes 1 unit of time to process any job. Although every server should finish working at the same time, we assume that server 0 finishes slightly faster server 1, server 1 finishes slightly faster than server 2, and so on. In this way we can distinguish the time that each job finished its processing. Finally, after each server finishes processing the current job, it takes next job in the queue to process for the next round.

Your task is to output the sequence of jobs that have been processed ordered by the time servers finish processing them.

Consider the following example where n=5, k=3, and the values of s are as follows:

i    s[i]
---------
0     0
1     2
2     0
3     1
4     2

After all tasks arrived, the queues at the servers are like these:

servers       job queues
-----------------------------------
0             0, 2
1             3
2             1, 4

After the first round where jobs 0, 3, 1 have been processed (in this order), the queues are like these:

servers       job queues
-----------------------------------
0             2
1             
2             4

In this 2nd round, jobs 2 and 4 have been processed (in this order), and there are no more jobs left.

The list of finished jobs (in the required order) is

0, 3, 1, 2, 4

Input/output

Input

• First line: integers n and k (1<=n<=100000; 1<=k<=100)
• Next n lines: each line 2+i, for 0 <= i < n, contains integer s[i], where 0 <= s[i] < k

Output There are n lines of output specifying jobs number in order that they have been processed.

Example

Input

5 3
0
2
0
1
2

Output

0
3
1
2
4

Test data

• Download here

Output for n20.in

0
1
4
3
2
9
5
8
11
6
14
13
7
16
17
10
19
12
15
18

First 10 lines of output for n100.in

0
3
4
1
17
5
2
22
6
8

Code

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private int n = 0;
    private int k = 0;
    private int [] s = null;
    
    public static void main(String[] args) {
        Main m = new Main();
        m.process();
    }

    private void process() {
        readInput();
        
        // ... your code here
    }
    
    private void readInput() {
        BufferedReader reader = new BufferedReader(
                   new InputStreamReader(System.in) );

        try {
            String[] items = reader.readLine().split(" ");
            n = Integer.parseInt(items[0]);
            k = Integer.parseInt(items[1]);
            s = new int[n];
            for(int i=0; i<n; i++) {
                s[i] = Integer.parseInt(reader.readLine());
            }
        } catch (Exception e) {
            System.out.println("Input error");
            n = 0; 
            k = 0;
        }
    }
}

Job queue 2

In this task, each job's requirement gets more complex. Each job can specified a list of servers that it has to goes through (in order) to get everything done.

You have n jobs to be executed in k servers, called server 0, server 1,..., and server k-1 (1 <= n <= 100,000; 1 <= k <= 100). These n jobs are job 0, job 1, job 2,..., job n-1. Each job i has to be processed by m[i] servers, specified by s[i][0], s[i][1], ..., s[i][m[i]-1]. After job i has been processed by all of these servers in this order, we say that job i has been completely processed.

All jobs arrive to our system in order from job 0 to job n-1, and when it arrives it goes to the first server that will process it. Each server processes jobs in the order that they arrive to the server. We assume that before the system starts processing any jobs, all jobs arrive at our system and are assigned to appropriate server queues.

The system works in synchronous rounds. Every server takes 1 unit of time to process any job. Although every server should finish working at the same time, we assume that server 0 finishes slightly faster server 1, server 1 finishes slightly faster than server 2, and so on. In this way we can distinguish the time that each job finished its processing. After each job has been processed by a server, if there are servers that it has to go to, it enters that server's queue. Finally, after each server finishes processing the current job and the processed unfinished jobs enter their next queue, each server takes next job in the queue to process for the next round.

Your task is to output the sequence of jobs that have been completely processed ordered by the time servers finish processing them.

Consider the following example where n=5, k=3, and the values of s are as follows:

i    m[i]   s[i][]
--------------------
0    1      0
1    3      2, 0, 1
2    2      0, 1
3    1      1
4    2      2, 1

After all tasks arrived, the queues at the servers are like these:

servers       job queues
-----------------------------------
0             0, 2
1             3
2             1, 4

After the first round where jobs 0, 3, 1 have been processed (in this order) and job 1 enters server 1's queue, the queues are like these:

servers       job queues
-----------------------------------
0             2, 1
1             
2             4

In this 2nd round, jobs 2 and 4 have been processed (in this order). Note that both jobs have to go to server 1, but job 2 finishes before job 4 (because of their servers) in this round; thus, job 2 enters the queue before job 4. The queue becomes

servers       job queues
-----------------------------------
0             1
1             2, 4
2             

After job 1 and 2 have been processed, the queue becomes

servers       job queues
-----------------------------------
0             
1             4, 1
2             

Then

servers       job queues
-----------------------------------
0             
1             1
2             

and after this, there are no more jobs.

The list of completely finished jobs is

0, 3, 2, 4, 1

Input/output

Input

First line: integers n and k Next n lines: each line 2+i, for 0 <= i < n, starts with an integer m[i] (1 <= m[i] <= 5) and then follows by m[i] integers: s[i][0], s[i][1], ... , s[i][m[i]-1], where 0 <= s[i][j] < k

Output There are n lines of output specifying jobs number in order that they have been completely processed.

Example 1

Input

5 3
1 0
3 2 0 1
2 0 1
1 1
2 2 1

Output

0
3
2
4
1

Example 2

Input

3 4
1 3
1 3
3 0 1 2

Output

0
1
2

Hints: If your output is 2 0 1, you have to look carefully on how to move jobs between queues.

Code

Job.java

public class Job {
    public int id;
    public int numSteps;
    public int[] serverIds;
    public int numStepsDone = 0;
    
    public Job(int id, String line) {
        this.id = id;
        
        String[] items = line.split(" ");
        numSteps = Integer.parseInt(items[0]);
        numStepsDone = 0;
        
        serverIds = new int[numSteps];
        for(int i=0; i<numSteps; i++) {
            serverIds[i] = Integer.parseInt(items[i+1]);
        }
    }

    public int getNextServerId() {
        return serverIds[numStepsDone];
    }

    public void markCurrentStepDone() {
        numStepsDone++;
    }
    
    public boolean isDone() {
        return numSteps == numStepsDone;
    }

    // added to help you debugging
    public String toString() {
        return "" + id + "(" + numStepsDone + "/" + numSteps + ")";
    }
}

Main.java

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private int n = 0;
    private int k = 0;
    private Job[] jobs;
    
    public static void main(String[] args) {
        Main m = new Main();
        m.process();
    }

    private void process() {
        readInput();
        // ... your code here
    }
    
    private void readInput() {
        BufferedReader reader = new BufferedReader(
                   new InputStreamReader(System.in) );

        try {
            String[] items = reader.readLine().split(" ");
            n = Integer.parseInt(items[0]);
            k = Integer.parseInt(items[1]);
            jobs = new Job[n];
            
            for(int i=0; i<n; i++) {
                jobs[i] = new Job(i, reader.readLine());
            }
        } catch (Exception e) {
            System.out.println("Input error");
            n = 0; 
            k = 0;
        }
    }
}