ในโรงงานของ JOI Co., Ltd. มีโต๊ะ $N$ ตัว หมายเลข $0$ ถึง $N-1$ และมีสายพานลำเลียง $N-1$ เส้น หมายเลข $0$ ถึง $N-2$ สายพานลำเลียง $i$ ($0\le i\le N-2$) เชื่อมโต๊ะ $A_i$ กับโต๊ะ $B_i$ และขนส่งสินค้าจากโต๊ะหนึ่งไปยังอีกโต๊ะหนึ่ง แต่เราไม่สามารถมองเห็นทิศทางการขนส่งได้ หากไม่สนใจทิศทางของสายพานลำเลียง โต๊ะทุกคู่จะเชื่อมถึงกันผ่านสายพานลำเลียงจำนวนหนึ่ง

IOI-kun เป็นผู้อำนวยการโรงงาน เนื่องจากเขาลืมทิศทางการขนส่งของสายพานทุกเส้น เขาจึงจะทำชุดขั้นตอนต่อไปนี้หลายครั้งตามลำดับ

1. เขาเลือกสายพานลำเลียงจำนวนหนึ่ง และกลับทิศทางการขนส่งของสายพานที่เลือก
2. เขาเลือกโต๊ะจำนวนหนึ่ง และวางสินค้าหนึ่งชิ้นบนโต๊ะที่เลือกแต่ละตัว

3. สำหรับโต๊ะทุกตัวที่วางสินค้าไว้ เหตุการณ์อย่างใดอย่างหนึ่งต่อไปนี้จะเกิดขึ้นพร้อมกัน

4. หากไม่มีสายพานลำเลียงขนส่งสินค้าออกจากโต๊ะนั้น จะไม่มีอะไรเกิดขึ้น

5. หากมีสายพานลำเลียงขนส่งสินค้าออกจากโต๊ะนั้น สินค้าบนโต๊ะจะถูกขนส่งโดยสายพานเส้นใดเส้นหนึ่งดังกล่าว สินค้าจะหยุดที่ปลายทางของสายพานและไม่เคลื่อนที่อีก

6. IOI-kun ตรวจสอบว่าแต่ละโต๊ะมีสินค้าอย่างน้อยหนึ่งชิ้นหรือไม่ หากมีสินค้าอยู่บนโต๊ะ เขาจะเก็บสินค้าทั้งหมดออก

7. สำหรับสายพานทุกเส้นที่ถูกกลับทิศทางในขั้นตอนที่ 1 IOI-kun จะกลับทิศทางคืนให้เป็นทิศทางเดิม

IOI-kun ต้องการระบุทิศทางเดิมของสายพานทุกเส้น โดยทำชุดขั้นตอนข้างต้นไม่เกิน $30$ ครั้ง

จงเขียนโปรแกรมที่รับข้อมูลเกี่ยวกับโต๊ะที่สายพานแต่ละเส้นเชื่อมอยู่ และทำตามกลยุทธ์ของ IOI-kun เพื่อระบุทิศทางเดิมของสายพานทุกเส้น โดยทำชุดขั้นตอนข้างต้นไม่เกิน $30$ ครั้ง

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

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

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

ใน conveyor.cpp ต้องเขียนฟังก์ชันต่อไปนี้

void Solve(int N, std::vector<int> A, std::vector<int> B)

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

• พารามิเตอร์ N คือจำนวนโต๊ะ $N$
• พารามิเตอร์ A, B เป็นอาร์เรย์ความยาว $N-1$ ซึ่งระบุโต๊ะที่สายพานแต่ละเส้นเชื่อมอยู่

โปรแกรมของคุณสามารถเรียกฟังก์ชันต่อไปนี้ได้

std::vector<int> Query(std::vector<int> x, std::vector<int> y)

IOI-kun ใช้ฟังก์ชันนี้เพื่อดำเนินขั้นตอนในโรงงาน

• พารามิเตอร์ x เป็นอาร์เรย์ความยาว $N-1$ สำหรับ $0\le i\le N-2$ IOI-kun จะกลับทิศทางของสายพาน $i$ หาก x[i] = 1 และจะไม่กลับทิศทางของสายพาน $i$ หาก x[i] = 0
• พารามิเตอร์ y เป็นอาร์เรย์ความยาว $N$ สำหรับ $0\le j\le N-1$ IOI-kun จะวางสินค้าบนโต๊ะ $j$ หาก y[j] = 1 และจะไม่วางสินค้าบนโต๊ะ $j$ หาก y[j] = 0
• ให้ z เป็นค่าที่ฟังก์ชันนี้ส่งกลับ ซึ่งเป็นอาร์เรย์ความยาว $N$ สำหรับ $0\le j\le N-1$ โต๊ะ $j$ มีสินค้าอย่างน้อยหนึ่งชิ้นหาก z[j] = 1 และไม่มีสินค้าหาก z[j] = 0
• ความยาวของอาร์เรย์ x ต้องเท่ากับ $N-1$ หากไม่เป็นไปตามเงื่อนไขนี้ โปรแกรมจะถูกตัดสินว่าคำตอบผิด (Wrong Answer [1])
• สมาชิกทุกตัวของอาร์เรย์ x ต้องเป็น $0$ หรือ $1$ หากไม่เป็นไปตามเงื่อนไขนี้ โปรแกรมจะถูกตัดสินว่าคำตอบผิด (Wrong Answer [2])
• ความยาวของอาร์เรย์ y ต้องเท่ากับ $N$ หากไม่เป็นไปตามเงื่อนไขนี้ โปรแกรมจะถูกตัดสินว่าคำตอบผิด (Wrong Answer [3])
• สมาชิกทุกตัวของอาร์เรย์ y ต้องเป็น $0$ หรือ $1$ หากไม่เป็นไปตามเงื่อนไขนี้ โปรแกรมจะถูกตัดสินว่าคำตอบผิด (Wrong Answer [4])
• ห้ามเรียกฟังก์ชัน Query เกิน $30$ ครั้ง หากเรียกเกิน $30$ ครั้ง โปรแกรมจะถูกตัดสินว่าคำตอบผิด (Wrong Answer [5])

void Answer(std::vector<int> a)

IOI-kun ใช้ฟังก์ชันนี้เพื่อรายงานทิศทางเดิมของสายพานแต่ละเส้น

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

ข้อควรระวังสำคัญ

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

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

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

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

g++ -std=gnu++17 -O2 -o grader grader.cpp conveyor.cpp

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

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

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

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

$$ \begin{array}{l} N\\ A_0\ A_1\ \cdots\ A_{N-2}\\ B_0\ B_1\ \cdots\ B_{N-2}\\ C_0\ C_1\ \cdots\ C_{N-2} \end{array} $$

สำหรับ $0\le i\le N-2$ จะมี $C_i=0$ หากสายพาน $i$ ขนส่งสินค้าจากโต๊ะ $A_i$ ไปยังโต๊ะ $B_i$ มิฉะนั้นจะมี $C_i=1$

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

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

• หากโปรแกรมถูกตัดสินว่าถูกต้อง จะรายงานจำนวนครั้งที่เรียก Query เช่น “Accepted: 22”
• หากโปรแกรมถูกตัดสินว่าคำตอบผิดประเภทใด ตัวตรวจตัวอย่างจะรายงานประเภทนั้น เช่น “Wrong Answer [4]”

หากโปรแกรมเข้าเงื่อนไขคำตอบผิดหลายประเภท ตัวตรวจตัวอย่างจะรายงานเพียงประเภทเดียว

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

./grader 2023

หมายเหตุเกี่ยวกับการตรวจ

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

ข้อจำกัด

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

• $0\le A_i\le N-1$ ($0\le i\le N-2$)
• $0\le B_i\le N-1$ ($0\le i\le N-2$)
• หากไม่สนใจทิศทางของสายพานลำเลียง โต๊ะทุกคู่จะเชื่อมถึงกันผ่านสายพานลำเลียงจำนวนหนึ่ง

งานย่อย

1. (1 คะแนน) $N=2$
2. (14 คะแนน) $N=30$
3. (10 คะแนน) $N=100\,000$, $A_i=i$ ($0\le i\le N-2$), $B_i=i+1$ ($0\le i\le N-2$)
4. (75 คะแนน) $N=100\,000$

ตัวอย่างการโต้ตอบ

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

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

3
0 2
2 1
1 0

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

สำหรับการเรียก Query ครั้งแรก นอกจาก [1, 0, 0] แล้ว ค่าที่ส่งกลับยังอาจเป็น [0, 1, 0] ได้ด้วย

สำหรับการเรียก Query ครั้งที่สอง สินค้าบนโต๊ะ $0$ จะถูกขนส่งไปยังโต๊ะ $2$ ผ่านสายพาน $0$ แล้วหยุดอยู่ที่นั่น โปรดทราบว่าสินค้าชิ้นนี้จะไม่ถูกขนส่งไปยังโต๊ะ $1$ ผ่านสายพาน $1$ ต่อ

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

ในบรรดาไฟล์ที่ดาวน์โหลดได้จากหน้าเว็บการแข่งขัน sample-02.txt เป็นไปตามข้อจำกัดของงานย่อย $1$ และ sample-03.txt เป็นไปตามข้อจำกัดของงานย่อย $2$