Anna dan Bruno adalah ahli judi. Mereka akan memainkan sebuah permainan bersama D-taro, yang menjadi bandar permainan tersebut.

Dalam permainan ini, Anna dan Bruno berada di ruangan yang berbeda. Mereka hanya dapat saling berkomunikasi menggunakan sebuah perangkat yang rusak. D-taro memberikan sebuah bilangan bulat kepada Anna. Tujuan Anna dan Bruno dalam permainan ini adalah mengirimkan bilangan bulat tersebut dari Anna kepada Bruno menggunakan perangkat itu.

Pada awal permainan, Anna terlebih dahulu menyatakan sebuah bilangan bulat $m$ antara $1$ dan $2\,000$, inklusif. Kemudian mereka memainkan $Q$ ronde. Ronde ke-$i$ ($1\le i\le Q$) dilakukan sebagai berikut.

1. D-taro memberikan sebuah bilangan bulat $A_i$ kepada Anna.
2. Anna memasukkan larik $s_i,t_i$ ke dalam perangkat. Setiap elemen larik $s_i,t_i$ harus bernilai $0$ atau $1$. Kedua larik harus memiliki panjang yang sama, dan panjangnya berada antara $1$ dan $m$, inklusif.
3. Misalkan $u_i$ adalah larik yang diperoleh dari $s_i$ dan $t_i$ melalui pengocokan berselang-seling (lihat di bawah). Perangkat kemudian mengirimkan $u_i$ kepada Bruno.
4. Bruno mengirimkan sebuah bilangan bulat kepada D-taro. Jika bilangan ini sama dengan bilangan bulat $A_i$ yang diberikan D-taro kepada Anna, Anna dan Bruno memenangkan ronde ini.

Tulislah program yang mengimplementasikan strategi Anna dan Bruno agar mereka menang dalam seluruh $Q$ ronde.

Pengocokan Berselang-seling

Kita mengatakan larik $Z$ diperoleh dari larik $X$ dan $Y$ melalui pengocokan berselang-seling jika elemen-elemen $Z$ dapat dibagi menjadi dua kelompok sehingga kedua syarat berikut terpenuhi.

• Larik yang terdiri dari elemen-elemen kelompok pertama dalam urutan semula sama dengan larik $X$.
• Larik yang terdiri dari elemen-elemen kelompok kedua dalam urutan semula sama dengan larik $Y$.

Sebagai contoh, larik $Z=[1,1,1,0,0,0]$ diperoleh dari $X=[1,1,0]$ dan $Y=[1,0,0]$ melalui pengocokan berselang-seling, karena larik yang terdiri dari elemen pertama, kedua, dan keempat $Z$ dalam urutan semula adalah $[1,1,0]$, dan larik yang terdiri dari elemen ketiga, kelima, dan keenam $Z$ dalam urutan semula adalah $[1,0,0]$.

Sebaliknya, jika $X=[1,1,0]$, $Y=[1,0,0]$, dan $Z=[0,0,0,1,1,1]$, larik $Z$ tidak diperoleh dari $X$ dan $Y$ melalui pengocokan berselang-seling.

Detail Implementasi

Anda harus mengumpulkan dua berkas.

Berkas pertama adalah Anna.cpp. Berkas ini harus mengimplementasikan strategi Anna dan fungsi-fungsi berikut. Program harus menyertakan Anna.h menggunakan direktif praprosesor #include.

• int Declare()

  Fungsi ini dipanggil sekali pada awal permainan.

  • Nilai kembaliannya adalah bilangan bulat $m$ yang dinyatakan Anna.
  • Bilangan bulat $m$ harus berada antara $1$ dan $2\,000$, inklusif. Jika syarat ini tidak terpenuhi, program Anda dinilai sebagai Wrong Answer [1].

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

  Setelah fungsi Declare dipanggil, fungsi ini dipanggil $Q$ kali. Pemanggilan ke-$i$ ($1\le i\le Q$) fungsi ini sesuai dengan Langkah 1 dan Langkah 2 pada ronde ke-$i$.

  • Parameter A adalah bilangan bulat $A_i$ yang diberikan D-taro kepada Anna.
  • Nilai kembaliannya adalah pasangan dua larik $s_i,t_i$ yang dimasukkan Anna ke dalam perangkat.
  • Setiap elemen larik $s_i,t_i$ harus bernilai $0$ atau $1$. Jika syarat ini tidak terpenuhi, program Anda dinilai sebagai Wrong Answer [2].
  • Panjang masing-masing larik $s_i,t_i$ harus berada antara $1$ dan $m$, inklusif. Jika syarat ini tidak terpenuhi, program Anda dinilai sebagai Wrong Answer [3].
  • Larik $s_i,t_i$ harus memiliki panjang yang sama. Jika syarat ini tidak terpenuhi, program Anda dinilai sebagai Wrong Answer [4].

Berkas kedua adalah Bruno.cpp. Berkas ini harus mengimplementasikan strategi Bruno dan fungsi berikut. Program harus menyertakan Bruno.h menggunakan direktif praprosesor #include.

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

  Setelah Anna memasukkan larik ke dalam perangkat, fungsi ini dipanggil sekali. Secara keseluruhan, fungsi ini dipanggil $Q$ kali. Pemanggilan ke-$i$ ($1\le i\le Q$) fungsi ini sesuai dengan Langkah 3 dan Langkah 4 pada ronde ke-$i$.

  • Parameter u adalah larik $u_i$ yang dikirimkan perangkat kepada Bruno pada ronde ke-$i$.
  • Nilai kembaliannya adalah bilangan bulat yang dikirimkan Bruno kepada D-taro.
  • Nilai kembaliannya harus sama dengan bilangan bulat $A_i$ yang diberikan D-taro kepada Anna. Jika syarat ini tidak terpenuhi, program Anda dinilai sebagai Wrong Answer [5].

Catatan Penting

• Program Anda boleh mengimplementasikan fungsi lain untuk penggunaan internal atau menggunakan variabel global. Berkas-berkas yang dikumpulkan akan dikompilasi bersama grader menjadi satu berkas yang dapat dieksekusi. Semua variabel global dan fungsi internal harus dideklarasikan dalam namespace tanpa nama agar tidak berbenturan dengan berkas lain. Saat dinilai, program dijalankan sebagai dua proses, yaitu proses Anna dan proses Bruno. Kedua proses tersebut tidak dapat berbagi variabel global.
• Program Anda tidak boleh menggunakan masukan standar maupun keluaran standar. Program Anda tidak boleh berkomunikasi dengan berkas lain dengan cara apa pun. Namun, program Anda boleh menuliskan informasi debugging ke keluaran galat standar.

Kompilasi dan Pengujian

Anda dapat mengunduh sebuah berkas arsip dari halaman web kontes yang berisi grader contoh untuk menguji program Anda. Arsip tersebut juga berisi contoh berkas kode sumber program Anda.

Grader contoh adalah berkas grader.cpp. Untuk menguji program Anda, letakkan grader.cpp, Anna.cpp, Bruno.cpp, Anna.h, dan Bruno.h dalam direktori yang sama, lalu jalankan perintah berikut untuk mengompilasi program.

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

Jika kompilasi berhasil, berkas yang dapat dieksekusi bernama grader akan dihasilkan.

Perhatikan bahwa grader sebenarnya berbeda dari grader contoh. Grader contoh dijalankan sebagai satu proses yang membaca data dari masukan standar dan menuliskan hasil ke keluaran standar.

Masukan untuk Grader Contoh

Grader contoh membaca data berikut dari masukan standar.

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

Keluaran Grader Contoh

Grader contoh menuliskan informasi berikut ke keluaran standar (tanda kutip digunakan agar jelas).

• Jika program Anda dinilai benar, grader menuliskan nilai kembalian $m$ dari fungsi Declare seperti Accepted: 2000.
• Jika program Anda dinilai sebagai salah satu jenis Wrong Answer, grader contoh menuliskan jenisnya seperti Wrong Answer [1].

Jika program Anda memenuhi kondisi beberapa jenis Wrong Answer, grader contoh hanya melaporkan salah satunya.

Saat grader contoh dijalankan, pengocokan berselang-seling untuk setiap ronde dihitung menggunakan bilangan acak semu. Hasilnya tidak berubah antareksekusi. Untuk mengubah seed bilangan acak semu, jalankan grader contoh dengan cara berikut.

./grader 2022

Argumen pertama harus berupa bilangan bulat.

Batasan

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

Subtugas

1. (5 poin) $A_i\le 2\,000$ ($1\le i\le Q$).
2. (5 poin) $A_i\le 4\,000\,000$ ($1\le i\le Q$).
3. (3 poin) $A_i\le 10\,000\,000\ (=10^7)$ ($1\le i\le Q$).
4. (12 poin) $A_i\le 100\,000\,000\ (=10^8)$ ($1\le i\le Q$).
5. (15 poin) $A_i\le 100\,000\,000\,000\ (=10^{11})$ ($1\le i\le Q$).

6. (60 poin) Tidak ada batasan tambahan. Untuk subtugas ini, skor Anda dihitung sebagai berikut.

   • Misalkan $m^*$ adalah nilai maksimum dari bilangan bulat $m$ yang dinyatakan Anna untuk semua kasus uji dalam subtugas ini.
   • Skor Anda adalah sebagai berikut.

Contoh Komunikasi

Berikut adalah contoh masukan untuk grader contoh dan pemanggilan fungsi yang bersesuaian.

Masukan 1

2
42
2000

Contoh Pemanggilan Fungsi

Dalam contoh masukan ini, terdapat $Q\ (=2)$ ronde. Pada ronde pertama, D-taro memberikan bilangan bulat $A_1\ (=42)$ kepada Anna. Pada ronde kedua, D-taro memberikan bilangan bulat $A_2\ (=2000)$ kepada Anna.

Contoh masukan ini memenuhi batasan semua subtugas.