JOI Co., Ltd. компаниясының зауытында $0$-ден $N-1$-ге дейін нөмірленген $N$ үстел бар. Зауытта $0$-ден $N-2$-ге дейін нөмірленген $N-1$ конвейер таспасы бар. $i$ ($0 \le i \le N-2$) конвейер таспасы $A_i$ үстелі мен $B_i$ үстелін жалғайды. Ол өнімдерді бір үстелден екінші үстелге тасымалдайды. Алайда біз тасымалдау бағытын көре алмаймыз. Егер конвейер таспаларының бағыттарын ескермесек, үстелдердің кез келген жұбы бірнеше конвейер таспасы арқылы өзара байланысқан.

IOI-кун — осы зауыттың директоры. Ол әрбір конвейер таспасының тасымалдау бағытын ұмытып қалғандықтан, келесі тізбектелген амалдарды бірнеше рет орындайды.

1. Ол бірнеше конвейер таспасын таңдап, таңдалған конвейер таспаларының тасымалдау бағыттарын қарама-қарсы бағытқа өзгертеді.
2. Ол бірнеше үстелді таңдап, таңдалған әрбір үстелдің үстіне бір өнімнен қояды.

3. Үстіне өнім қойылған әрбір үстел үшін бір мезгілде келесі жағдайлардың бірі орын алады.

   • Егер осы үстелден өнімдерді алып кететін конвейер таспасы болмаса, ештеңе болмайды.
   • Егер осы үстелден өнімдерді алып кететін конвейер таспалары болса, үстелдегі өнім сондай конвейер таспаларының бірімен тасымалданады. Өнім сол конвейер таспасының баратын үстелінде тоқтайды. Өнім одан әрі қозғалмайды.

4. IOI-кун әрбір үстелде бір немесе одан көп өнім бар-жоғын тексереді. Егер үстелде өнімдер болса, IOI-кун олардың барлығын жинап алады.

5. 1-амалда бағыты өзгертілген әрбір конвейер таспасы үшін IOI-кун оның бағытын қайтадан қалпына келтіреді. Оның бағыты бастапқы бағытына айналады.

IOI-кун жоғарыдағы тізбектелген амалдарды ең көп дегенде $30$ рет орындау арқылы әрбір конвейер таспасының бастапқы бағытын анықтағысы келеді.

Конвейер таспаларымен жалғанған үстелдер туралы ақпарат берілгенде, жоғарыдағы тізбектелген амалдарды ең көп дегенде $30$ рет орындау арқылы әрбір конвейер таспасының бастапқы бағытын анықтайтын IOI-кунның стратегиясын іске асыратын программа жазыңыз.

Іске асыру мәліметтері

Сізге бір файл жіберу қажет.

Файл атауы — conveyor.cpp. Ол келесі функцияны іске асыруы керек. Программа #include препроцессор директивасын қолданып conveyor.h файлын қосуы тиіс.

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-кун зауыттағы амалдарды орындайды.

    • x параметрі — ұзындығы $N-1$ болатын массив. $0 \le i \le N-2$ үшін, егер x[i] = 1 болса, IOI-кун $i$ конвейер таспасының бағытын қарама-қарсы өзгертеді, ал егер x[i] = 0 болса, $i$ конвейер таспасының бағытын өзгертпейді.
    • y параметрі — ұзындығы $N$ болатын массив. $0 \le j \le N-1$ үшін, егер y[j] = 1 болса, IOI-кун $j$ үстеліне өнім қояды, ал егер y[j] = 0 болса, $j$ үстеліне өнім қоймайды.
    • z осы функцияның қайтаратын мәні болсын. Ол — ұзындығы $N$ болатын массив. $0 \le j \le N-1$ үшін, егер z[j] = 1 болса, $j$ үстелінде бір немесе одан көп өнім бар деген сөз, ал егер z[j] = 0 болса, $j$ үстелінде өнім жоқ деген сөз.
    • 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-кун әрбір конвейер таспасының бастапқы бағытын хабарлайды.

    • 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-кун қандай да бір конвейер таспасының бағытын қате хабарласа, программаңыз Wrong Answer [8] деп бағаланады.
    • Answer функциясы дәл бір рет шақырылуы керек. Егер Answer функциясы бір реттен артық шақырылса, программаңыз Wrong Answer [9] деп бағаланады. Solve функциясы жұмысын аяқтаған кезде Answer функциясы шақырылмаған болса, программаңыз Wrong Answer [10] деп бағаланады.

Маңызды ескертулер

• Сіздің программаңыз ішкі қажеттіліктер үшін басқа функцияларды іске асыра алады немесе глобалды айнымалыларды қолдана алады.
• Сіздің программаңыз стандартты енгізуді және стандартты шығаруды қолданбауы тиіс. Сіздің программаңыз ешқандай әдіспен басқа файлдармен байланыспауы тиіс. Дегенмен, программаңыз стандартты қателер ағынына (standard error) жөндеу (debugging) ақпаратын шығара алады.

Компиляция және сынақ ретінде іске қосу

Сіз жарыс веб-бетінен программаңызды тексеруге арналған үлгі грейдері бар архив файлын жүктей аласыз. Архив файлында программаңыздың үлгі бастапқы код файлы да бар.

Үлгі грейдер — grader.cpp файлы. Программаңызды тексеру үшін grader.cpp, conveyor.cpp, conveyor.h файлдарын бір директорияға орналастырып, программаларды компиляциялау үшін келесі команданы орындаңыз. Оның орнына архив файлындағы compile.sh скриптін іске қосуға да болады.

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

Компиляция сәтті аяқталғанда, grader орындалатын файлы жасалады.

Нақты грейдер үлгі грейдерден өзгеше екенін ескеріңіз. Үлгі грейдер стандартты енгізуден деректерді оқып, нәтижелерді стандартты шығаруға жазатын жалғыз процесс ретінде іске қосылады.

Үлгі грейдерге арналған енгізу деректері

Үлгі грейдер стандартты енгізуден келесі деректерді оқиды.

$$ \begin{array}{llll} 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$ үшін, егер $i$ конвейер таспасы өнімдерді $A_i$ үстелінен $B_i$ үстеліне тасымалдаса, $C_i=0$ болады. Әйтпесе, $C_i=1$ болады.

Үлгі грейдердің шығару деректері

Үлгі грейдер стандартты шығаруға келесі ақпаратты шығарады (тырнақшалар түсінікті болу үшін берілген).

• Егер программаңыз дұрыс деп танылса, ол Query функциясын шақыру санын “Accepted: 22” түрінде хабарлайды.
• Егер программаңыз Wrong Answer-дің қандай да бір түрі ретінде бағаланса, үлгі грейдер оның түрін “Wrong Answer [4]” сияқты жазады.

Егер программаңыз бірнеше Wrong Answer түрінің шарттарын қанағаттандырса, үлгі грейдер олардың тек біреуін ғана хабарлайды.

Үлгі грейдерде үстіне өнім қойылған үстелден өнімдерді алып кететін конвейер таспаларының ішінен өнімді тасымалдайтын конвейер таспасы әртүрлі іске қосулар кезінде нәтижелері өзгермейтін жалған кездейсоқ сандар арқылы бірқалыпты және кездейсоқ түрде таңдалады. Жалған кездейсоқ сандардың бастапқы мәнін (seed) өзгерту үшін, үлгі грейдерді бірінші бүтін санды аргументпен келесідей іске қосыңыз.

./grader 2023

Бағалау бойынша ескертулер

Кейбір тест жағдайлары үшін нақты грейдер бейімделгіш (adaptive) болып табылады. Бұл грейдердің басында бекітілген жауабы болмайтынын және ол алдыңғы 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$ үстеліндегі өнім $0$ конвейер таспасы арқылы $2$ үстеліне тасымалданады және сонда тоқтайды. Бұл өнім $1$ конвейер таспасы арқылы $1$ үстеліне тасымалданбайтынына назар аударыңыз.

Бұл енгізу мысалы ешбір ішкі есептің шектеулерін қанағаттандырмайтынын ескеріңіз.

Жарыс веб-бетінен алуға болатын файлдардың ішінде sample-02.txt файлы $1$-ішкі есептің шектеулерін қанағаттандырады, ал sample-03.txt файлы $2$-ішкі есептің шектеулерін қанағаттандырады.