2032 : ARCHERY
Problem type : Batch
Time limit : 2.0 second(s)
Memory limit : 64 megabyte(s)

การแข่งขันยิงธนูได้ถูกจัดขึ้นตามหลักเกณฑ์ต่าง ๆ   ดังนี้   มีเป้ายิงทั้งหมด N เป้าถูกจัดเรียงในแนวเส้นตรงและมีหมายเลขตั้งแต่ 1 ถึง N ตามตำแหน่งของพวกมันบนแนวเส้นตรงนั้น (เป้ายิงทางซ้ายมือสุดจะเป็นเป้ายิงหมายเลขที่ 1 และเป้ายิงทางขวามือสุดจะเป็นเป้ายิงหมายเลขที่ N)   นอกจากนี้ ยังมีผู้ยิงธนูทั้งหมด 2N  คน   ในระหว่างการแข่งขัน จะมีผู้ยิงธนู 2 คนต่อ 1 เป้ายิงทุกครั้งและในทุกรอบการแข่งขันจะดำเนินไปตามขั้นตอนต่าง ๆ    ดังนี้

 

ผู้ยิงธนูทั้ง 2 คนในแต่ละเป้ายิงจะแข่งขันกันเพื่อหาผู้ชนะและผู้แพ้ในระหว่างพวกเขา   จากนั้น  ผู้ยิงธนูทุกคนจะเรียงตัวกันใหม่ ดังนี้

  •  ผู้ชนะที่เป้ายิงตั้งแต่หมายเลขที่ 2 ถึงหมายเลขที่ N ให้เคลื่อนที่ไปยังเป้ายิงที่อยู่ทางซ้ายมือของพวกเขา (ยกตัวอย่าง เช่น เป้ายิงหมายเลขที่ 1 ถึง N-1   ตามลำดับ)
  • ผู้แพ้ที่เป้ายิงตั้งแต่หมายเลขที่ 2 ถึงหมายเลขที่ N และผู้ชนะที่เป้ายิงหมายเลขที่ 1   ให้ยืนอยู่ที่เป้ายิงเดิม
  • ผู้แพ้ที่เป้ายิงหมายเลขที่ 1 ให้เคลื่อนที่ไปยังเป้ายิงหมายเลขที่ N

 

การแข่งขันนี้จะดำเนินไปทั้งหมด R รอบการแข่งขัน โดยจำนวนที่น้อยที่สุดของรอบการแข่งขันจะมากกว่าหรือเท่ากับจำนวนผู้ยิงธนู (ยกตัวอย่าง เช่น   R 2N)

 

คุณคือผู้ยิงธนูคนเดียวเท่านั้นที่มาถึงการแข่งขันตรงเวลา   ส่วนผู้ยิงธนูอีก 2N - 1 คนได้มาถึงก่อนหน้านี้และได้ยืนเรียงแถวกันในแนวเส้นตรงเรียบร้อยแล้ว   สิ่งที่คุณต้องทำตอนนี้คือแทรกตัวเองเข้าไปที่จุด ๆ หนึ่งในแถวของพวกเขา   และหลังจากที่คุณเข้าประจำที่เรียบร้อยแล้ว   ผู้ยิงธนูที่อยู่ตำแหน่งทางซ้ายมือสุดทั้ง 2 คนในแถวจะเริ่มการแข่งขันในเป้ายิงหมายเลขที่ 1   แล้วผู้ยิงธนูที่อยู่ถัดไปอีก 2 คนจะเริ่มแข่งขันกันในเป้ายิงหมายเลขที่ 2   และเป็นเช่นนี้เรื่อยไปจนกระทั่งผู้ยิงธนูที่อยู่ตำแหน่งขวามือสุดทั้ง 2 คนแข่งขันกันในเป้ายิงหมายเลขที่ N

 

ผู้ยิงธนูทั้งหมด  2N  คนในการแข่งขัน (ซึ่งรวมทั้งตัวคุณเองด้วย) จะถูกจัดลำดับตามทักษะความสามารถ   โดยผู้ที่มีลำดับที่ต่ำกว่าจะหมายถึงผู้ที่มีทักษะเหนือกว่า   ไม่มีผู้ยิงธนู 2 คนใด ๆ ที่มีหมายเลขลำดับเดียวกัน   นอกจากนี้ เมื่อใดก็ตามที่ผู้ยิงธนู 2 คนแข่งขันกัน   ผู้ที่มีหมายเลขลำดับต่ำกว่าจะเป็นผู้ชนะเสมอ

 

เมื่อคุณรู้ทักษะความสามารถของผู้เข้าแข่งขันแต่ละคนแล้ว   คุณก็อยากที่จะแทรกตัวคุณเองเข้าไปในตำแหน่งที่คุณจะแน่ใจได้ว่า   คุณจะได้จบการแข่งขันในเป้ายิงหมายเลขที่น้อยที่สุดเท่าที่จะเป็นไปได้    และถ้ามีหนทางหลากหลายที่จะทำแบบนี้ได้   คุณจะชอบหนทางที่คุณจะได้เริ่มต้นการแข่งขันในเป้ายิงหมายเลขที่มากที่สุดที่จะเป็นไปได้มากกว่าหนทางอื่น

งานของคุณ

จงเขียนโปรแกรมเพื่อรับหมายเลขลำดับแสดงทักษะความสามารถของผู้ยิงธนูทุกคน รวมทั้งตัวคุณเองด้วย   และค่าการเรียงแถวในแนวเส้นตรงของคู่แข่งของคุณ   แล้วพิจารณาหาหมายเลขของเป้ายิงที่คุณจะใช้เริ่มต้นการแข่งขัน   เพื่อให้บรรลุตามวัตถุประสงค์ของคุณตามที่ได้กล่าวถึงไว้ก่อนหน้านี้แล้ว

เงื่อนไข

1 N 200 000    คือ จำนวนของเป้ายิงซึ่งจะต้องเท่ากับครึ่งหนึ่งของจำนวนผู้เข้าแข่งขันยิงธนู

2N R 1 000 000 000   คือจำนวนรอบการแข่งขัน

1 Sk 2N   คือ หมายเลขลำดับแสดงทักษะความสามารถของผู้ยิงธนูคนที่ k

ข้อมูลนำเข้า

โปรแกรมของคุณจะต้องอ่านข้อมูลจากคีย์บอร์ด (standard input)   ดังนี้

ในบรรทัดแรก   ประกอบด้วยเลขจำนวนเต็ม N และ R ซึ่งแยกกันด้วยช่องว่าง

แต่ละ 2N บรรทัดถัดมา   ห้ลงรายการของหมายเลขลำดับแสดงทักษะความสามารถของผู้ยิงธนูแต่ละคน   โดยในบรรทัดแรกจะเป็นหมายเลขลำดับทักษะของคุณ   ส่วนบรรทัดอื่น ๆ ที่เหลือจะเป็นหมายเลขลำดับทักษะของผู้ยิงธนูที่เหลือ   ผู้ยิงธนู 1 คนต่อ 1 บรรทัดตามลำดับที่พวกเขายืนเรียงแถวกันในแนวเส้นตรง (จากซ้ายไปขวา)    ในแต่ละ 2N บรรทัดเหล่านี้จะประกอบด้วยเลขจำนวนเต็มเพียงค่าเดียวที่มีค่าตั้งแต่ 1 ถึง 2N    โดยหมายเลขลำดับแสดงทักษะหมายเลขที่ 1 หมายถึงคนที่เก่งที่สุดและหมายเลขลำดับแสดงทักษะที่ 2N จะหมายถึงที่คนที่แย่ที่สุด   และไม่มีผู้ยิงธนู 2 คนใด ๆ ที่มีหมายเลขลำดับเดียวกัน

ข้อมูลส่งออก

โปรแกรมของคุณจะต้องเขียนข้อมูลออกมาทางจอภาพ (standard output) ภายในบรรทัดเดียว   ซี่งประกอบด้วยเลขจำนวนเต็มเพียงค่าเดียวที่มีค่าตั้งแต่ 1 ถึง N   แสดงหมายเลขของเป้ายิงที่คุณจะใช้เริ่มต้นการแข่งขัน

การให้คะแนน
สำหรับการทดสอบ จะมีค่า 60 คะแนน เมื่อ N มีค่าไม่เกิน 5000
และสำหรับบางส่วนของการทดสอบเหล่านี้ จะมีค่า 20 คะแนน เมื่อ N มีค่าไม่เกิน 200

ที่มา: 21-st International Olympiad In Informatics August 8 - 15, 2009 (Day 1)


ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
4 8
7
4
2
6
5
8
1
3
3
4 9
2
1
5
8
3
4
7
6
2

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 19 ผู้เยี่ยมชมและ 2 สมาชิก (1 บอท)