บนเครื่องจักรเครื่องหนึ่ง มีงานที่เป็นอิสระต่อกันจำนวน $n$ งานกำลังรอการจัดตาราง งานที่เริ่มทำงานในเวลา $t$ จะเสร็จสิ้นในเวลา $t+1$ งานทั้งหมดสามารถเริ่มได้ในเวลาที่เป็นจำนวนเต็มเท่านั้น เมื่องานหนึ่งเสร็จสิ้น สามารถเริ่มงานอื่นได้ทันที ในระหว่างที่งานหนึ่งกำลังทำงานอยู่ จะไม่สามารถทำงานอื่นได้
แต่ละงานมีข้อจำกัดด้านเวลา ซึ่งสามารถแสดงได้ดังนี้: เวลาเริ่มต้นของงานที่ $i$ จะต้องอยู่ระหว่างเวลา $l_i$ ถึงเวลา $r_i$ (รวมขอบทั้งสองข้าง)
นอกจากนี้ ยังมีข้อกำหนดอีก $m$ ข้อ ข้อกำหนดที่ $j$ ระบุว่า ในระหว่างเวลา $p_j$ ถึงเวลา $q_j$ (รวมขอบทั้งสองข้าง) จะสามารถเริ่มงานได้มากที่สุดเพียงหนึ่งงานเท่านั้น
จงหาเวลาเริ่มต้นของแต่ละงานที่สอดคล้องกับเงื่อนไขข้างต้นทั้งหมด
ข้อมูลนำเข้า
โจทย์ข้อนี้มีข้อมูลทดสอบหลายชุด
บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็มไม่ลบ $T$ แทนจำนวนชุดข้อมูลทดสอบ
จากนั้นเป็นข้อมูลของแต่ละชุดข้อมูลทดสอบตามลำดับ สำหรับแต่ละชุดข้อมูลทดสอบ:
บรรทัดแรกประกอบด้วยจำนวนเต็มสองจำนวน คือ $n$ และ $m$
อีก $n$ บรรทัดถัดมา แต่ละบรรทัดประกอบด้วยจำนวนเต็มสองจำนวน คือ $l_i$ และ $r_i$ แทนช่วงเวลาที่สามารถเริ่มได้ของงานที่ $i$
อีก $m$ บรรทัดถัดมา แต่ละบรรทัดประกอบด้วยจำนวนเต็มสองจำนวน คือ $p_j$ และ $q_j$ แทนช่วงเวลาของข้อกำหนดการจัดตารางที่ $j$
ข้อมูลส่งออก
สำหรับข้อมูลแต่ละชุด ให้แสดงผลหนึ่งบรรทัดประกอบด้วยจำนวนเต็ม $n$ จำนวน แทนเวลาเริ่มต้นของแต่ละงานตามลำดับ โดยเฉพาะอย่างยิ่ง หากไม่มีแผนการจัดตารางที่เป็นไปได้ ให้แสดงผล Impossible หากมีแผนที่เป็นไปได้หลายแบบ สามารถแสดงผลแบบใดก็ได้
ตัวอย่างที่ 1
ข้อมูลนำเข้า
4 2 3 2 7 1 10 7 8 2 10 1 6 2 2 2 5 1 9 1 5 4 9 2 4 3 8 3 6 2 7 4 7 8 9 1 6 4 1 6 7 6 7 6 7 1 11 21 31
ข้อมูลส่งออก
7 1 3 9 8 6 Impossible
หมายเหตุ
ตัวอย่างนี้สอดคล้องกับข้อจำกัดของงานย่อยที่ $1$
- สำหรับข้อมูลชุดที่หนึ่ง งานทั้งสองเริ่มในเวลา $7,1$ ตามลำดับ ซึ่งทั้งคู่อยู่ในช่วง $[l,r]$ ของตนเอง และสอดคล้องกับข้อกำหนดทั้งหมด
- สำหรับข้อมูลชุดที่สี่ งานสามงานแรกสามารถเริ่มได้ในเวลา $6$ หรือ $7$ เท่านั้น ดังนั้นจึงไม่มีแผนการจัดตารางที่เป็นไปได้
ตัวอย่างที่ 2
ดูไฟล์ ex_data2.in และ ex_data2.ans ในไฟล์ที่แจกให้
ตัวอย่างนี้สอดคล้องกับข้อจำกัดของงานย่อยที่ $2$
ตัวอย่างที่ 3
ดูไฟล์ ex_data3.in และ ex_data3.ans ในไฟล์ที่แจกให้
ตัวอย่างนี้สอดคล้องกับข้อจำกัดของงานย่อยที่ $3$
ตัวอย่างที่ 4
ดูไฟล์ ex_data4.in และ ex_data4.ans ในไฟล์ที่แจกให้
ตัวอย่างนี้สอดคล้องกับข้อจำกัดของงานย่อยที่ $4$
ตัวอย่างที่ 5
ดูไฟล์ ex_data5.in และ ex_data5.ans ในไฟล์ที่แจกให้
ตัวอย่างนี้สอดคล้องกับข้อจำกัดของงานย่อยที่ $5$
ตัวอย่างที่ 6
ดูไฟล์ ex_data6.in และ ex_data6.ans ในไฟล์ที่แจกให้
ตัวอย่างนี้สอดคล้องกับข้อจำกัดของงานย่อยที่ $6$
ตัวอย่างที่ 7
ดูไฟล์ ex_data7.in และ ex_data7.ans ในไฟล์ที่แจกให้
ตัวอย่างนี้สอดคล้องกับข้อจำกัดของงานย่อยที่ $7$
ตัวอย่างที่ 8
ดูไฟล์ ex_data8.in และ ex_data8.ans ในไฟล์ที่แจกให้
ตัวอย่างนี้สอดคล้องกับข้อจำกัดของงานย่อยที่ $8$
ข้อจำกัด
กำหนดให้ $N,M$ เป็นผลรวมของ $n,m$ ของชุดข้อมูลทดสอบทั้งหมดในหนึ่งชุดทดสอบตามลำดับ สำหรับข้อมูลทดสอบทั้งหมดจะมี:
- $1 \le n \le 2.5 \times 10^5,0 \le m \le 2.5 \times 10^5$;
- $1 \le l_i \le r_i \le 10^{9}$;
- $1 \le p_j \le q_j \le 10^{9}$.
| งานย่อยที่ | $N\le$ | $M\le$ | คุณสมบัติพิเศษ | คะแนน |
|---|---|---|---|---|
| $1$ | $10$ | $10$ | ไม่มี | $5$ |
| $2$ | $2.5\times 10^5$ | $2.5\times 10^5$ | $\rm A$ | $5$ |
| $3$ | $10^3$ | $10^3$ | $\rm B$ | $15$ |
| $4$ | $2.5\times 10^5$ | $2.5\times 10^5$ | $\rm C$ | $15$ |
| $5$ | $10^4$ | $10^4$ | $\rm B$ | $15$ |
| $6$ | $10^5$ | $10^5$ | $\rm B$ | $15$ |
| $7$ | $10^5$ | $10^5$ | ไม่มี | $15$ |
| $8$ | $2.5\times 10^5$ | $2.5\times 10^5$ | ไม่มี | $15$ |
$\rm A$: รับประกันว่า $n\le100$ และสำหรับทุก $1\le i< n$ จะมี $l_i\le l_{i+1}$ และ $r_i\le r_{i+1}$
$\rm B$: สำหรับทุก $1\le i\le n$ จะมี $r_i\le 5\max(n,m)$
$\rm C$: สำหรับทุก $1\le i\le m$ จะมี $p_i=i,q_i=i+1$ และสำหรับทุก $1\le i\le n$ จะมี $r_i\le m$