ملّ 小E حساب بواقي إجابات المسائل الغريبة بترديد $998244353$ أو $10^9+7$، فصمّم لغزًا يتعلق بالعدد $2$:

تُعطى شبكة من صفين و-$2^k$ عمودًا. عليك ملء خلاياها البالغ عددها $2^{k+1}$ بالأعداد من $1$ إلى $2^{k+1}$، دون تكرار أو إغفال، بحيث تستوفي علاقات المقارنة بين الخلايا المتجاورة القيود التالية.

تحديدًا، تُعطى ثلاث متتاليات ثنائية $a,b,c$ أطوالها على الترتيب $2^k-1,2^k,2^k-1$. تُعدّ المصفوفة $A$ ذات الأبعاد $2\times2^k$ حلًا للغز إذا وفقط إذا استوفت القيود الأربعة جميعها:

1. تحتوي $A$ على كل عدد صحيح من $1,2,\ldots,2^{k+1}$ مرة واحدة بالضبط.
2. لكل $1\le i<2^k$، يتحقق $a_i=[A_{1,i}<A_{1,i+1}]$.
3. لكل $1\le i\le2^k$، يتحقق $b_i=[A_{1,i}<A_{2,i}]$.
4. لكل $1\le i<2^k$، يتحقق $c_i=[A_{2,i}<A_{2,i+1}]$.

حيث تكون قيمة $[P]$ هي $1$ إذا تحقق الشرط $P$، وتكون $0$ خلاف ذلك.

إيجاد أي حل أو تقرير عدم وجود حل أمر سهل جدًا بالنسبة إليك. ولأن اللغز يتعلق بالعدد $2$، يطلب منك 小E حساب عدد حلول اللغز بترديد $2$.

أعدّ 小E عددًا قدره $t$ من الألغاز ذات حجم الشبكة نفسه، وضغطها معًا بطريقة فعّالة. عليك حساب عدد الحلول بترديد $2$ لكل لغز منها.

تفاصيل التنفيذ

لا يحتاج المتسابق إلى تنفيذ الدالة main، ويجب ألا ينفذها.

يجب أن يتضمن البرنامج المقدّم ملف الترويسة puzzle.h، وذلك بإضافة الكود التالي في بدايته:

#include "puzzle.h"

عليك تنفيذ الدالة التالية في الملف المصدري المقدّم:

unsigned puzzle(int t, int k, std::vector<unsigned> a,
                std::vector<unsigned> b, std::vector<unsigned> c);

• يمثّل $t,k$ عدد الألغاز وحجم الشبكة، على الترتيب.
• لكل $0\le i<2^k-1$، يمثّل البت رقم $j$ ($0\le j<t$) في التمثيل الثنائي لـ $a_i$ قيد المقارنة بين $A_{1,i+1}$ و-$A_{1,i+2}$ في اللغز رقم $j+1$.
• لكل $0\le i<2^k$، يمثّل البت رقم $j$ ($0\le j<t$) في التمثيل الثنائي لـ $b_i$ قيد المقارنة بين $A_{1,i+1}$ و-$A_{2,i+1}$ في اللغز رقم $j+1$.
• لكل $0\le i<2^k-1$، يمثّل البت رقم $j$ ($0\le j<t$) في التمثيل الثنائي لـ $c_i$ قيد المقارنة بين $A_{2,i+1}$ و-$A_{2,i+2}$ في اللغز رقم $j+1$.
• يجب أن تعيد الدالة عددًا صحيحًا غير سالب، يمثّل البت رقم $j$ ($0\le j<t$) في تمثيله الثنائي عدد حلول اللغز رقم $j+1$ بترديد $2$.
• في كل اختبار، تستدعي مكتبة التفاعل هذه الدالة مرة واحدة بالضبط.

ملاحظة: في جميع الحالات، لا يتجاوز زمن تشغيل مكتبة التفاعل $0.1$ ثانية، واستهلاكها للذاكرة ثابت ولا يتجاوز $64$ MiB.

اختبار البرنامج

الملف grader.cpp في مجلد المسألة هو تنفيذ مرجعي لمكتبة التفاعل. التنفيذ المستخدم في التقييم النهائي يختلف عنه، لذا يجب ألا يعتمد حلك على تفاصيل تنفيذ المكتبة.

يمكنك الترجمة من داخل مجلد المسألة بالأمر التالي لإنشاء ملف تنفيذي:

g++ grader.cpp puzzle.cpp -o puzzle -O2 -std=c++14 -static

بالنسبة إلى الملف التنفيذي الناتج:

• يقرأ البيانات من الإدخال القياسي بالصيغة التالية:
  • يحتوي السطر الأول على عددين صحيحين موجبين $t,k$، يمثّلان عدد الألغاز وحجم الشبكة.
  • يحتوي السطر $3i-1$ ($1\le i\le t$) على سلسلة ثنائية $a_1\ldots a_{2^k-1}$ طولها $2^k-1$.
  • يحتوي السطر $3i$ ($1\le i\le t$) على سلسلة ثنائية $b_1\ldots b_{2^k}$ طولها $2^k$.
  • يحتوي السطر $3i+1$ ($1\le i\le t$) على سلسلة ثنائية $c_1\ldots c_{2^k-1}$ طولها $2^k-1$.
• يكتب البيانات إلى الإخراج القياسي بالصيغة التالية:
  • يتكون الإخراج من $t$ أسطر. يحتوي السطر $i$ ($1\le i\le t$) على عدد صحيح غير سالب، يمثّل عدد حلول اللغز $i$ بترديد $2$.

أمثلة

الإدخال 1

2 1
1
01
1
1
00
1

الإخراج 1

1
0

الإدخال 2

4 2
100
1111
100
100
0000
110
110
1111
011
010
0000
010

الإخراج 2

1
1
0
0

الملفات الإضافية

تتضمن الملفات الإضافية:

1. grader.cpp، وهو التنفيذ المرجعي المقدّم لمكتبة التفاعل.
2. puzzle.h، وهو ملف الترويسة؛ لا تحتاج إلى الاهتمام بتفاصيل محتواه.
3. template_puzzle.cpp، وهو كود نموذجي يمكنك الرجوع إليه لتنفيذ كودك.

المهام الفرعية

في جميع بيانات الاختبار:

• $1\le t\le32$، $1\le k\le18$.
• لكل $1\le i<2^k$، يكون $a_i\in\{0,1\}$.
• لكل $1\le i\le2^k$، يكون $b_i\in\{0,1\}$.
• لكل $1\le i<2^k$، يكون $c_i\in\{0,1\}$.

الخاصية الخاصة A: $t\le4$.

الخاصية الخاصة B: لكل $1\le i<2^k$، يتحقق $b_i\ne b_{i+1}$.

التقييم

ملاحظة:

• يجب ألا يحصل المتسابق على معلومات داخلية من مكتبة التفاعل بطرق غير مشروعة، كالتعامل مباشرة مع مجريَي الإدخال والإخراج القياسيين. يُعدّ ذلك غشًا.
• تنفيذ مكتبة التفاعل المستخدمة في التقييم النهائي مختلف عن تنفيذ مكتبة المثال.

تخضع المسألة أولًا للقيود نفسها التي تخضع لها المسائل التقليدية. على سبيل المثال، يؤدي خطأ الترجمة إلى الحصول على $0$ في المسألة بأكملها، ويؤدي خطأ التشغيل أو تجاوز حد الزمن أو حد الذاكرة ونحو ذلك إلى الحصول على $0$ في الاختبار المعني. لا يجوز للبرنامج الوصول إلا إلى المتغيرات التي يعرّفها المتسابق أو التي تقدمها مكتبة التفاعل؛ قد تؤدي محاولة الوصول إلى مساحات عناوين أخرى إلى خطأ ترجمة أو تشغيل.

وبناءً على ما سبق:

• يحصل البرنامج على الدرجة الكاملة في اختبار إذا وفقط إذا كانت الإجابة التي تعيدها الدالة puzzle صحيحة.