Anna และ Bruno เป็นยอดฝีมือด้านการพนัน ทั้งสองจะเล่นเกมกับ D-taro ซึ่งเป็นเจ้ามือของเกม

ในเกมนี้ Anna และ Bruno อยู่คนละห้อง และสื่อสารกันได้ผ่านอุปกรณ์ที่ชำรุดเท่านั้น D-taro จะให้จำนวนเต็มแก่ Anna เป้าหมายของ Anna และ Bruno คือส่งจำนวนเต็มนั้นจาก Anna ไปยัง Bruno โดยใช้อุปกรณ์นี้

เมื่อเกมเริ่ม Anna จะประกาศจำนวนเต็ม $m$ ระหว่าง $1$ ถึง $2\,000$ รวมปลายทั้งสองก่อน จากนั้นจะเล่นทั้งหมด $Q$ รอบ โดยรอบที่ $i$ ($1\le i\le Q$) ดำเนินการดังนี้

1. D-taro ให้จำนวนเต็ม $A_i$ แก่ Anna
2. Anna ป้อนอาร์เรย์ $s_i,t_i$ เข้าอุปกรณ์ สมาชิกทุกตัวของทั้งสองอาร์เรย์ต้องเป็น $0$ หรือ $1$ อาร์เรย์ทั้งสองต้องยาวเท่ากัน และมีความยาวระหว่าง $1$ ถึง $m$ รวมปลายทั้งสอง
3. ให้ $u_i$ เป็นอาร์เรย์ที่ได้จากการสับสอดประสานอาร์เรย์ $s_i$ และ $t_i$ (ดูด้านล่าง) แล้วอุปกรณ์ส่ง $u_i$ ไปยัง Bruno
4. Bruno ส่งจำนวนเต็มให้ D-taro หากจำนวนนี้ตรงกับ $A_i$ ที่ D-taro ให้ Anna ทั้ง Anna และ Bruno จะชนะรอบนั้น

จงเขียนโปรแกรมที่ใช้กลยุทธ์ของ Anna และ Bruno เพื่อให้ชนะทั้ง $Q$ รอบ

การสับสอดประสาน

เรากล่าวว่าอาร์เรย์ $Z$ ได้จากการสับสอดประสานอาร์เรย์ $X$ และ $Y$ หากสามารถแบ่งสมาชิกของ $Z$ เป็นสองกลุ่มโดยเป็นไปตามเงื่อนไขสองข้อต่อไปนี้

• อาร์เรย์ที่ประกอบด้วยสมาชิกในกลุ่มแรกตามลำดับเดิม เท่ากับอาร์เรย์ $X$
• อาร์เรย์ที่ประกอบด้วยสมาชิกในกลุ่มที่สองตามลำดับเดิม เท่ากับอาร์เรย์ $Y$

ตัวอย่างเช่น $Z=[1,1,1,0,0,0]$ ได้จากการสับสอดประสาน $X=[1,1,0]$ และ $Y=[1,0,0]$ เพราะสมาชิกตัวที่หนึ่ง สอง และสี่ของ $Z$ ตามลำดับเดิมเป็นอาร์เรย์ $[1,1,0]$ ส่วนสมาชิกตัวที่สาม ห้า และหกตามลำดับเดิมเป็นอาร์เรย์ $[1,0,0]$

ในทางกลับกัน หาก $X=[1,1,0]$, $Y=[1,0,0]$ และ $Z=[0,0,0,1,1,1]$ จะไม่สามารถสร้าง $Z$ จากการสับสอดประสาน $X$ และ $Y$ ได้

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

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

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

• int Declare()

  ฟังก์ชันนี้ถูกเรียกหนึ่งครั้งเมื่อเริ่มต้น

  • ค่าที่คืนคือจำนวนเต็ม $m$ ที่ Anna ประกาศ
  • $m$ ต้องอยู่ระหว่าง $1$ ถึง $2\,000$ รวมปลายทั้งสอง มิฉะนั้นโปรแกรมจะถูกตัดสินเป็น Wrong Answer [1]

• std::pair<std::vector<int>, std::vector<int> > Anna(long long A)

  หลังจากเรียก Declare ฟังก์ชันนี้จะถูกเรียก $Q$ ครั้ง การเรียกครั้งที่ $i$ ($1\le i\le Q$) ตรงกับขั้นตอนที่ 1 และ 2 ของรอบที่ $i$

  • พารามิเตอร์ A คือจำนวนเต็ม $A_i$ ที่ D-taro ให้ Anna
  • ค่าที่คืนคือคู่อาร์เรย์ $s_i,t_i$ ที่ Anna ป้อนเข้าอุปกรณ์
  • สมาชิกทุกตัวของ $s_i,t_i$ ต้องเป็น $0$ หรือ $1$ มิฉะนั้นโปรแกรมจะถูกตัดสินเป็น Wrong Answer [2]
  • ความยาวของทั้ง $s_i$ และ $t_i$ ต้องอยู่ระหว่าง $1$ ถึง $m$ รวมปลายทั้งสอง มิฉะนั้นโปรแกรมจะถูกตัดสินเป็น Wrong Answer [3]
  • อาร์เรย์ $s_i,t_i$ ต้องยาวเท่ากัน มิฉะนั้นโปรแกรมจะถูกตัดสินเป็น Wrong Answer [4]

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

• long long Bruno(std::vector<int> u)

  หลังจาก Anna ป้อนอาร์เรย์เข้าอุปกรณ์ ฟังก์ชันนี้จะถูกเรียกหนึ่งครั้ง รวมทั้งหมด $Q$ ครั้ง การเรียกครั้งที่ $i$ ($1\le i\le Q$) ตรงกับขั้นตอนที่ 3 และ 4 ของรอบที่ $i$

  • พารามิเตอร์ u คืออาร์เรย์ $u_i$ ที่อุปกรณ์ส่งให้ Bruno ในรอบที่ $i$
  • ค่าที่คืนคือจำนวนเต็มที่ Bruno ส่งให้ D-taro
  • ค่าที่คืนต้องเท่ากับ $A_i$ ที่ D-taro ให้ Anna มิฉะนั้นโปรแกรมจะถูกตัดสินเป็น Wrong Answer [5]

ข้อควรทราบ

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

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

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

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

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

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

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

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

โปรแกรมตรวจตัวอย่างอ่านข้อมูลต่อไปนี้จากอินพุตมาตรฐาน

$$ \begin{array}{l} Q\\ A_1\\ A_2\\ \vdots\\ A_Q \end{array} $$

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

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

• หากโปรแกรมของคุณถูกตัดสินว่าถูกต้อง จะแสดงค่า $m$ ที่ฟังก์ชัน Declare คืนมา เช่น Accepted: 2000
• หากโปรแกรมถูกตัดสินเป็น Wrong Answer ประเภทใดประเภทหนึ่ง โปรแกรมตรวจตัวอย่างจะแสดงประเภทนั้น เช่น Wrong Answer [1]

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

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

./grader 2022

อาร์กิวเมนต์ตัวแรกต้องเป็นจำนวนเต็ม

ข้อจำกัด

• $1\le Q\le1\,000$
• $1\le A_i\le1\,000\,000\,000\,000\,000\,000$ ($=10^{18}$) ($1\le i\le Q$)

งานย่อย

1. (5 คะแนน) $A_i\le2\,000$ ($1\le i\le Q$)
2. (5 คะแนน) $A_i\le4\,000\,000$ ($1\le i\le Q$)
3. (3 คะแนน) $A_i\le10\,000\,000$ ($=10^7$) ($1\le i\le Q$)
4. (12 คะแนน) $A_i\le100\,000\,000$ ($=10^8$) ($1\le i\le Q$)
5. (15 คะแนน) $A_i\le100\,000\,000\,000$ ($=10^{11}$) ($1\le i\le Q$)

6. (60 คะแนน) ไม่มีข้อจำกัดเพิ่มเติม คะแนนของงานย่อยนี้คำนวณดังนี้

   • ให้ $m^*$ เป็นค่ามากที่สุดของจำนวนเต็ม $m$ ที่ Anna ประกาศในทุกกรณีทดสอบของงานย่อยนี้
   • คะแนนของคุณเป็นดังต่อไปนี้

ตัวอย่างการสื่อสาร

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

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

2
42
2000

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

ในตัวอย่างนี้มี $Q=2$ รอบ รอบที่ 1 D-taro ให้จำนวนเต็ม $A_1=42$ แก่ Anna และรอบที่ 2 ให้จำนวนเต็ม $A_2=2000$ แก่ Anna

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