เมื่อเวลาผ่านไปหลายร้อยปี JOI city ก็กลายเป็นเมืองร้าง IOI-chan ซึ่งเป็นนักสำรวจกำลังสำรวจบริเวณที่เคยสร้างห้องสมุด จากผลการสำรวจ เราทราบข้อมูลต่อไปนี้:

• ในห้องสมุดของ JOI city เคยมีชั้นวางหนังสือแนวนอน ซึ่งมีตำแหน่งสำหรับวางหนังสือเรียงกัน $N$ ตำแหน่ง หมายเลข $0$ ถึง $N-1$ จากซ้ายไปขวา แต่ละตำแหน่งวางหนังสือได้พอดีหนึ่งเล่ม
• เคยมีหนังสือ $N$ เล่มบนชั้นวาง หนังสือทั้ง $N$ เล่มมีหมายเลข $0$ ถึง $N-1$
• การจัดเรียงหนังสือคือวิธีวางหนังสือทั้ง $N$ เล่มลงในตำแหน่งทั้ง $N$ ตำแหน่ง
• หนังสือมีการจัดเรียงที่ถูกต้อง โดยในการจัดเรียงที่ถูกต้อง หนังสือ $B_i$ ($0\le i\le N-1$) อยู่ที่ตำแหน่ง $i$ และค่า $B_i$ ทั้งหมดแตกต่างกัน

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

การดำเนินการ: ให้หนังสือ $x$ เป็นหนังสือที่อยู่ซ้ายสุดในบรรดาหนังสือที่ตำแหน่งปัจจุบันแตกต่างจากตำแหน่งในการจัดเรียงที่ถูกต้อง และให้หนังสือ $y$ เป็นหนังสือที่ปัจจุบันอยู่ ณ ตำแหน่งที่หนังสือ $x$ อยู่ในการจัดเรียงที่ถูกต้อง สลับตำแหน่งของหนังสือ $x$ และหนังสือ $y$

แม้ IOI-chan จะพบหนังสือเก่าของห้องสมุดแล้ว แต่เธอก็ไม่อาจทราบการจัดเรียงที่ถูกต้อง อย่างไรก็ตาม เธอพบเครื่องจักรเก่าที่เคยจัดการการดำเนินการของชั้นวางหนังสือในห้องสมุด หากเราระบุการจัดเรียงหนังสือทั้ง $N$ เล่มแล้วส่งคำถามไปยังเครื่องจักร เครื่องจักรจะตอบจำนวนการดำเนินการที่จำเป็นเพื่อจัดหนังสือทั้งหมดกลับสู่การจัดเรียงที่ถูกต้อง IOI-chan ต้องการทราบการจัดเรียงหนังสือที่ถูกต้องด้วยการส่งคำถามไปยังเครื่องจักร เนื่องจากเครื่องจักรเก่าแล้ว เธอจึงส่งคำถามไปยังเครื่องจักรได้ไม่เกิน $5\,000$ ครั้ง

จงเขียนโปรแกรมที่เมื่อได้รับข้อมูลของชั้นวางหนังสือ จะระบุการจัดเรียงหนังสือที่ถูกต้องด้วยการส่งคำถามไม่เกิน $5\,000$ ครั้ง

รายละเอียดการเขียนโปรแกรม

คุณต้องส่งไฟล์หนึ่งไฟล์

ไฟล์นั้นคือ library3.cpp ซึ่งต้องเขียนฟังก์ชันต่อไปนี้ โปรแกรมต้องรวม library3.h ด้วยคำสั่งประมวลผลก่อน #include

• void solve(int N)

  ฟังก์ชันนี้จะถูกเรียกเพียงครั้งเดียวสำหรับแต่ละกรณีทดสอบ

  • พารามิเตอร์ N คือจำนวนหนังสือ $N$

ใน library3.cpp คุณสามารถเรียกฟังก์ชันต่อไปนี้ได้

• int query(const std::vector<int> a)

  IOI-chan ใช้ฟังก์ชันนี้เพื่อส่งคำถามไปยังเครื่องจักร

  • พารามิเตอร์ a เป็นอาร์เรย์ความยาว $N$ ซึ่งระบุการจัดเรียงหนังสือ $N$ เล่มสำหรับคำถาม กล่าวคือ ในการจัดเรียงที่ระบุ หนังสือ a[i] ($0\le i\le N-1$) ต้องอยู่ที่ตำแหน่ง $i$
  • ค่าที่คืนมาคือจำนวนการดำเนินการที่จำเป็นเพื่อจัดหนังสือทั้งหมดกลับสู่การจัดเรียงที่ถูกต้อง โดยเริ่มจากการจัดเรียงที่ระบุ
  • ความยาวของพารามิเตอร์ a ต้องเท่ากับ $N$ หากไม่เป็นไปตามเงื่อนไขนี้ โปรแกรมจะถูกตัดสินเป็น Wrong Answer [1]
  • สมาชิกแต่ละตัวของพารามิเตอร์ a ต้องอยู่ระหว่าง $0$ และ $N-1$ หากไม่เป็นไปตามเงื่อนไขนี้ โปรแกรมจะถูกตัดสินเป็น Wrong Answer [2]
  • สมาชิกแต่ละตัวของพารามิเตอร์ a ต้องแตกต่างจากสมาชิกอื่นทั้งหมด หากไม่เป็นไปตามเงื่อนไขนี้ โปรแกรมจะถูกตัดสินเป็น Wrong Answer [3]
  • คุณต้องไม่เรียกฟังก์ชัน query เกิน $5\,000$ ครั้ง หากเรียกเกิน $5\,000$ ครั้ง โปรแกรมจะถูกตัดสินเป็น Wrong Answer [4]

• void answer(std::vector<int> b)

  โปรแกรมของคุณตอบการจัดเรียงหนังสือที่ถูกต้องด้วยการเรียกฟังก์ชันนี้

  • พารามิเตอร์ b เป็นอาร์เรย์ความยาว $N$ ซึ่งระบุการจัดเรียงหนังสือ $N$ เล่มในคำตอบ กล่าวคือ ในการจัดเรียงที่ตอบ หนังสือ b[i] ($0\le i\le N-1$) ต้องอยู่ที่ตำแหน่ง $i$
  • ความยาวของพารามิเตอร์ b ต้องเท่ากับ $N$ หากไม่เป็นไปตามเงื่อนไขนี้ โปรแกรมจะถูกตัดสินเป็น Wrong Answer [5]
  • สมาชิกแต่ละตัวของพารามิเตอร์ b ต้องอยู่ระหว่าง $0$ และ $N-1$ หากไม่เป็นไปตามเงื่อนไขนี้ โปรแกรมจะถูกตัดสินเป็น Wrong Answer [6]
  • สมาชิกแต่ละตัวของพารามิเตอร์ b ต้องแตกต่างจากสมาชิกอื่นทั้งหมด หากไม่เป็นไปตามเงื่อนไขนี้ โปรแกรมจะถูกตัดสินเป็น Wrong Answer [7]
  • การจัดเรียงที่ตอบต้องเป็นการจัดเรียงที่ถูกต้อง หากไม่เป็นไปตามเงื่อนไขนี้ โปรแกรมจะถูกตัดสินเป็น Wrong Answer [8]
  • ต้องเรียกฟังก์ชัน answer พอดีหนึ่งครั้ง หากเรียกมากกว่าหนึ่งครั้ง โปรแกรมจะถูกตัดสินเป็น Wrong Answer [9] เมื่อฟังก์ชัน solve จบการทำงาน หากยังไม่ได้เรียกฟังก์ชัน answer โปรแกรมจะถูกตัดสินเป็น Wrong Answer [10]

ข้อควรทราบสำคัญ

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

การคอมไพล์และทดสอบ

คุณสามารถดาวน์โหลดไฟล์บีบอัดจากหน้าเว็บการแข่งขัน ซึ่งมีตัวตรวจตัวอย่างสำหรับทดสอบโปรแกรมของคุณ ไฟล์บีบอัดยังมีไฟล์ซอร์สตัวอย่างของโปรแกรมของคุณด้วย

ตัวตรวจตัวอย่างคือไฟล์ grader.cpp หากต้องการทดสอบโปรแกรม ให้วาง grader.cpp, library3.cpp, library3.h ไว้ในไดเรกทอรีเดียวกัน แล้วเรียกคำสั่งต่อไปนี้เพื่อคอมไพล์โปรแกรม หรือจะเรียก compile.sh ที่อยู่ในไฟล์บีบอัดแทนก็ได้

g++ -std=gnu++20 -O2 -o grader grader.cpp library3.cpp

เมื่อคอมไพล์สำเร็จ จะสร้างไฟล์ปฏิบัติการ grader

โปรดทราบว่าตัวตรวจจริงแตกต่างจากตัวตรวจตัวอย่าง ตัวตรวจตัวอย่างจะทำงานเป็นโพรเซสเดียว โดยอ่านข้อมูลนำเข้าจากข้อมูลนำเข้ามาตรฐานและเขียนผลลัพธ์ไปยังข้อมูลส่งออกมาตรฐาน

ข้อมูลนำเข้าของตัวตรวจตัวอย่าง

ตัวตรวจตัวอย่างอ่านข้อมูลต่อไปนี้จากข้อมูลนำเข้ามาตรฐาน

$$ \begin{array}{l} N\\ B_0\ B_1\ \cdots\ B_{N-1} \end{array} $$

$B_i$ ($0\le i\le N-1$) คือหมายเลขหนังสือที่อยู่ ณ ตำแหน่ง $i$ ในการจัดเรียงที่ถูกต้อง

ข้อมูลส่งออกของตัวตรวจตัวอย่าง

ตัวตรวจตัวอย่างส่งข้อมูลต่อไปนี้ไปยังข้อมูลส่งออกมาตรฐานและข้อผิดพลาดมาตรฐาน (ใช้เครื่องหมายอัญประกาศเพื่อความชัดเจน)

• หากโปรแกรมของคุณถูกตัดสินว่าถูกต้อง จะรายงานจำนวนครั้งที่เรียก query ในรูปแบบ “Accepted: 3000”
• หากโปรแกรมของคุณถูกตัดสินเป็น Wrong Answer ประเภทใดก็ตาม ตัวตรวจตัวอย่างจะเขียนประเภทนั้นในรูปแบบ “Wrong Answer [3]”

หากโปรแกรมของคุณเข้าเงื่อนไข Wrong Answer หลายประเภท ตัวตรวจตัวอย่างจะรายงานเพียงประเภทเดียว

ข้อจำกัด

ข้อมูลนำเข้าทั้งหมดเป็นไปตามเงื่อนไขต่อไปนี้

• $2\le N\le 500$
• $0\le B_i\le N-1$ ($0\le i\le N-1$)
• $B_i\ne B_j$ ($0\le i<j\le N-1$)
• ค่าที่กำหนดทั้งหมดเป็นจำนวนเต็ม

งานย่อย

1. (2 คะแนน) $N\le 6$
2. (19 คะแนน) $N\le 100$
3. (79 คะแนน) ไม่มีข้อจำกัดเพิ่มเติม

ตัวอย่าง

ต่อไปนี้เป็นข้อมูลนำเข้าตัวอย่างสำหรับตัวตรวจตัวอย่างและการเรียกฟังก์ชันที่สอดคล้องกัน

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

4
2 0 3 1

ตัวอย่างการเรียกฟังก์ชัน

หมายเหตุ

ตัวอย่างเช่น การเรียก query([0, 1, 2, 3]) ระบุการจัดเรียงที่หนังสือ 0, 1, 2, 3 อยู่ ณ ตำแหน่ง 0, 1, 2, 3 ตามลำดับ การดำเนินการจะถูกทำซ้ำดังนี้

1. สลับตำแหน่งของหนังสือ 0 และหนังสือ 1 หนังสือ 1, 0, 2, 3 อยู่ ณ ตำแหน่ง 0, 1, 2, 3 ตามลำดับ
2. สลับตำแหน่งของหนังสือ 1 และหนังสือ 3 หนังสือ 3, 0, 2, 1 อยู่ ณ ตำแหน่ง 0, 1, 2, 3 ตามลำดับ
3. สลับตำแหน่งของหนังสือ 3 และหนังสือ 2 หนังสือ 2, 0, 3, 1 อยู่ ณ ตำแหน่ง 0, 1, 2, 3 ตามลำดับ

เนื่องจากจำนวนการดำเนินการที่จำเป็นเพื่อจัดหนังสือทั้งหมดกลับสู่การจัดเรียงที่ถูกต้องคือ 3 ค่าที่คืนจึงเป็น 3

ข้อมูลนำเข้าตัวอย่างนี้เป็นไปตามข้อจำกัดของงานย่อยทั้งหมด