oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

scheduler Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

scheduler.html

Problem Description

Rar the cat wants to hold a party for N people on a certain day. However, each person can only attend the party on certain periods of time. Therefore, Rar the cat has requested 2 integers from all it's attendees, A and B, meaning that this particular attendee can attend the party if it is held between Day A to Day B inclusive. Today will be counted as Day 0 and tomorrow would be Day 1, so on and so forth. (Eg. If today is Monday and A = 1, B = 3. It means that this attendee can attend the party from Tuesday to Thursday)

Rar the cat wants to hold the party on the day where the most number of people can attend, and he wants it as early as possible! As the number of people he has invited is too large for him to manually sort through and devise a suitable day to hold the party. He wants you to code a scheduler, that will tell him when is the earliest possible day where he can hold the party such that the maximum number of people could attend.

However, although a year has only about 365 days and a century has about 36525 days, he wants the scheduler to be able to handle infinitely large numbers of A and B, to avoid the end-of-the-world confusion that when A and B exceeds the integer limit (231), similar to the Mayan calendar.

Input

You are to input from standard input.

The first line of input consists of a single integer, N.

Subsequent N lines will consist of 2 integers each A and B, separated by a single space.

Output

You are to output to standard output.

Output a single integer, the earliest possible day where Rar the cat can hold the party where the most number of people can attend.

Limits

Subtask 1 (4%): N = 2, 0 ≤ A ≤ B ≤ 3000.

Subtask 2 (12%): N ≤ 3000, 0 ≤ A ≤ B ≤ 3000.

Subtask 3 (21%): N ≤ 100000, 0 ≤ A ≤ B ≤ 100000.

Subtask 4 (29%): N ≤ 100000, 0 ≤ A ≤ B ≤ 2000000000.

Subtask 5 (34%): N ≤ 100000, 0 ≤ A ≤ B ≤ 10100.

Subtask 6 (0%): As per sample testcases.

Implementation Details

You are strongly advised to use scanf and printf for this problem due to the large amounts of input. However, you are still allowed to use cin/cout. Invigilators will consider accepting your solution if the maximum execution time borders around the time limit(+10~20%) and has an accepted answer/solution.

Sample Testcase 1

This testcase adheres to the limits of subtask 2 to 5 only.

Input:

5
2 9
9 13
10 13
13 15
11 15

Output:

13

Holding the party on Day 13 will allow 4 people to attend the party, the maximum possible number of people attending.

Sample Testcase 2

This testcase adheres to the limits of subtask 2 to 5 only.

Input:

5
2 9
7 10
8 9
10 13
10 12

Output:

8

Holding the party on Day 8 will have the maximum of 3 people attending. Although holding the party on Day 10 will also result in 3 people attending, Rar the cat wants to hold the party as fast as possible, thus the scheduler should output 8 instead.

Sample Testcase 3

This testcase adheres to the limits of subtask 5 only.

Input:

5
2000000000000000000000000 9000000000000000000000000
7000000000000000000000000 10000000000000000000000000
8000000000000000000000000 9000000000000000000000000
10000000000000000000000000 13000000000000000000000000
10000000000000000000000000 12000000000000000000000000

Output:

8000000000000000000000000

Same reason as Sample Testcase 2, just that A and B in the input are very very large.

scheduler.pdf

Your browser does not support embedded PDF files. Please download the PDF instead.

mayan_unix.jpg

scheduler.docx

Tags

Raffles Cat Helping Contest 2013

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1452s256MBMinimum
21252s256MBMinimum
32152s256MBMinimum
42952s256MBMinimum
53452s256MBMinimum
6032s256MBMinimum

Attachments

Attachment Filesize Last Updated
scheduler_sample.zip814B31 Jan 2013, 15:13:55

Judge Compile Command

g++-8 ans.cpp -o scheduler -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.