في مصنع 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. يتحقق IOI-kun مما إذا كان يوجد منتج واحد أو أكثر على كل طاولة. إذا وجدت منتجات على طاولة، فإنه يأخذها كلها.

5. يعيد IOI-kun عكس اتجاه كل سير ناقل عُكس اتجاهه في العملية 1، فيعود اتجاهه إلى الاتجاه الأصلي.

يريد 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، ولا يعكسه إذا كان x[i] = 0.
• المعامل y مصفوفة بطول $N$. لكل $0\le j\le N-1$، يضع IOI-kun منتجًا على الطاولة $j$ إذا كان y[j] = 1، ولا يضع منتجًا عليها إذا كان y[j] = 0.
• لتكن z القيمة المعادة من هذه الدالة، وهي مصفوفة بطول $N$. لكل $0\le j\le N-1$، يوجد منتج واحد أو أكثر على الطاولة $j$ إذا كان z[j] = 1، ولا يوجد منتج عليها إذا كان z[j] = 0.
• يجب أن يكون طول المصفوفة x مساويًا لـ$N-1$. إذا لم يتحقق هذا الشرط، يُحكم على برنامجك بأنه إجابة خاطئة [1].
• يجب أن يكون كل عنصر في المصفوفة x إما 0 أو 1. إذا لم يتحقق هذا الشرط، يُحكم على برنامجك بأنه إجابة خاطئة [2].
• يجب أن يكون طول المصفوفة y مساويًا لـ$N$. إذا لم يتحقق هذا الشرط، يُحكم على برنامجك بأنه إجابة خاطئة [3].
• يجب أن يكون كل عنصر في المصفوفة y إما 0 أو 1. إذا لم يتحقق هذا الشرط، يُحكم على برنامجك بأنه إجابة خاطئة [4].
• يجب ألا تُستدعى الدالة Query أكثر من 30 مرة. إذا استُدعيت أكثر من 30 مرة، يُحكم على برنامجك بأنه إجابة خاطئة [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$. إذا لم يتحقق هذا الشرط، يُحكم على برنامجك بأنه إجابة خاطئة [6].
• يجب أن يكون كل عنصر في المصفوفة a إما 0 أو 1. إذا لم يتحقق هذا الشرط، يُحكم على برنامجك بأنه إجابة خاطئة [7].
• إذا أبلغ IOI-kun عن اتجاه خاطئ لأحد السيور الناقلة، يُحكم على برنامجك بأنه إجابة خاطئة [8].
• يجب استدعاء الدالة Answer مرة واحدة بالضبط. إذا استُدعيت أكثر من مرة، يُحكم على برنامجك بأنه إجابة خاطئة [9]. وإذا انتهت الدالة Solve دون استدعاء 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. (نقطة واحدة) $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، توجد قيمة معادة ممكنة أخرى هي [0, 1, 0]، إلى جانب [1, 0, 0].

في الاستدعاء الثاني للدالة Query، يُنقل المنتج الموجود على الطاولة $0$ إلى الطاولة $2$ عبر السير الناقل $0$، ويتوقف هناك. لاحظ أن هذا المنتج لن يُنقل إلى الطاولة $1$ عبر السير الناقل $1$.

لاحظ أن هذا الإدخال التجريبي لا يستوفي قيود أي مهمة فرعية.

من بين الملفات المتاحة من صفحة المسابقة، يستوفي sample-02.txt قيود المهمة الفرعية 1، ويستوفي sample-03.txt قيود المهمة الفرعية 2.