National Olympiad in Informatics, China, 2011

Day 2, Problem 2 - NOI Carnival

NOI 2011 at Jilin University has started! To welcome outstanding informatics competitors from across the country, Jilin University has decided to host two magnificent NOI carnivals at two different venues. Each venue contains many different events, and each event can only be held in one of the venues.

Little Andy, the carnival event organizer, has received a total of n event applications. The i-th event starts at S_i and has a duration of T_i. Each events may be scheduled at any one venue, or not scheduled at all.

After extensive surveying, Andy discovered that at any given time if both venues are simultaneously hosting events (excluding the instant when events start or end), competitors will be distraught over deciding between which venue to attend. To prevent this unpleasant scenario, Andy requires that no two events may be simultaneously held at both venues. Multiple events at the same venue may be held as pleased.

As one may imagine, if a certain venue contains too few events, then its appeal will not be so great, leading to an deserted site. Andy wishes to make an appropriate schedule such that the number of events at the venue with the fewest events is as large as possible.

Additionally, some events are very interesting and Andy would like to try to host them. He wishes to know, if the i-th event must be held (it may be held at either one of the venues), what is the maximum number of events than can be held at the venue with the fewest events.

Input Format

The first line contains an integer n, representing the number of events.
For the following n lines, each line describes a single event. The i-th of these lines will contain two integers S_i and T_i, indicating that event i will start at S_i and last T_i units of time.

Output Format

The first line of output should contain a single integer, representing the maximum number of events than can be held at the venue with the fewest events, without any extra restrictions about which event must be held.
The following n lines should each contain a single integer. The i-th of these lines should contain the maximum number of events than can be held at the venue with the fewest events, under the precondition that event i must be held.

Sample Input

5
8 2
1 5
5 3
3 2
5 3

Sample Output

2
2
1
2
2
2

Explanation

When there are no extra constraints, events 1 and 4 should be scheduled at one venue, and events 3 and 5 should be scheduled at the other venue. event 2 is not scheduled.

Scoring

For each test case, your score out of 10 is determined as follows:

• If the output format is invalid (e.g. there are fewer than n + 1 lines), then your score will be 0.
• If the first line is incorrect, and at least one of the following n lines is incorrect, then your score will be 0.
• If the first line is correct, but at least one of the following n lines is incorrect, then your score will be 4.
• If the first line is incorrect, but all of the following n lines are correct, then your score will be 6.
• If all n + 1 lines in the output are correct, then your score will be 10.

Constraints

The attributes of all the test cases are outlined below.

All Submissions
Best Solutions

Point Value: 25 (partial)
Time Limit: 1.00s
Memory Limit: 256M
Added: Aug 10, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

I could not get any points for just printing a correct answer on the first line even though I printed n + 1 lines. 

Sorry about that. The checker wasn't linked. I've rejudged and it should be working now.