TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

79.2% (38/48)

Submission's AC Ratio

17.2% (63/367)

Description

踏上旅程的小向,過不了多久就遇到了暴風雨。「雖然很想早點完成試練早點成為魔法少女,但在暴風雨中什麼事也做不了,只好先找個躲雨的地方過夜了…」小向獨自碎碎唸著。為了躲雨,小向必須盡快找到一間仍然有空房的旅館借宿一宿。不過走了許久,小向卻連半間旅館都沒見到。

這時,一名陌生的男子走了過來。

「你要找旅館吧?」
「!!」心思彷彿被摸透了般,小向聽到了這句話後不由自主地往後退了三步。
「別緊張別緊張。『讀心術』聽過吧?應該不是什麼怪事吧?」見到小向慌張的樣子,這名男子急忙解釋道。
「我剛好知道前面不遠處有間旅館,那裡應該還有空位。不過,既然目的是成為魔法少女,怎麼連個讀心術都不會呢…」男子騷騷頭,用不知道是驚訝還是挑釁的語氣說道。
「誰…誰說我不會讀心術的…我…我可是見習魔法少女小向呢!」小向握緊拳頭,手臂向下一揮,上半身微微前傾,用盡了全力向男子大吼。
「這樣啊…那麼…我心裡現在想的數字是什麼呢?」
「……」被識破不會讀心術的小向低頭沉默不語。
「果然還是太難了啊,那麼給你一些線索吧。」男子搖搖頭,接著繼續說道:
「首先,我心裡想的數字是一個$2^ {17} = 131072$位的,由0和1所構成的數字,不過我猜即使知道了這個,你也猜不出我心裡想的數字吧。這樣好了,你每次可以從這131072個位置中挑選幾個,而我會告訴你這幾個位置中1的個數是奇數還是偶數。只要使用限定次數內的詢問一次正確地答出我心裡想的數字的話我就帶你去旅館。如何?」

聽到這有如挑戰狀的敘述,小向馬上繃緊神經,心想:「我說什麼也不能輸給這個大叔!」不過冷靜一想,這不是很容易嗎?只要一個一個位置慢慢問,問131072次就結束了。正當小向覺得勝券在握時,男子的聲音中斷了她的喜悅。

「不過……」男子臉角微微上揚,
「我可是會說謊的喔…」

這麼一來小向說什麼也不可能回答出正確的內容。好險小向會讓人誠實的魔法ーー誠實豆沙包。找到了一絲希望的小向,馬上開始唸起咒語,構築魔法陣。周圍的空氣流動逐漸急遽,那名男子漸漸被圍繞起來。

「這是!」男子驚訝道,但他的身影緊接著就消失在陣陣旋風裡。魔法陣逐漸收斂。眼看著誠實豆沙包就要發揮他的作用,小向突然察覺到了異象。
「碰!」沒想到男子一吼就破解了誠實豆沙包。「真是有驚無險,不過看來你的魔法也不起作用了。來吧,開始猜我心中的數字吧。」

「少騙人了。」小向微笑道。
「大葛格,你已經只能再說一次謊囉~」小向用有點腹黑的語氣威脅道。
「嘖,被發現了嗎,還真有一套…」男子無奈地回答。

那麼,遊戲開始囉!

Input Format

本題沒有輸入,如果你輸入了任何東西,可能會導致各種不可預期的結果。

對於每筆測資,你只需要猜一次數字。
請記得#include "lib1945.h"。以下是幾個你可以使用的函式:

void Init():請在程式一開始呼叫這個函式。如果沒有呼叫這個函式就呼叫其它函式,你會獲得一個WA。

int Query(int n, int a[]):這個函數會回傳第a[0],a[1],...,a[n-1]這幾個位置中1的個數是奇數還是偶數(注意每筆測資中這個函數可能會說謊至多一次)。如果是奇數則回傳1,偶數則回傳0。如果呼叫這個函數超過$K$次,你會獲得一個WA。此外,如果n是負的,a[0],a[1],...,a[n-1]中有重複的,小於0的,或大於131071的,你都會獲得一個WA。如果陣列a的長度不到n可能會引發RE或是MLE。這個函式的複雜度是$O(n)$。

子任務(測資) 額外限制 分數
1 (0~4) $K=2^ {18}+1=262145$ 16
2 (5~9) $K=3\times 2^{16} + 2=199610$ 20
3 (10~14) $K=2^{17}+34=131106$ 28
4 (15~19) $K=2^ {17}+19=131091$ 36

Output Format

請出輸一行,包含用空白隔開的131072個0或1,代表你認為的答案。第$i$個數字代表第$i-1$位。

Sample Input

Sample Output

Hints

「不錯嘛…不論是誠實豆沙包的使用時機還是足以猜出我心中數字的機智…儘管作為魔法師的潛力還沒被引發出來,不過頭腦倒是夠靈活。」
「是魔法少女。」小向反駁道。
「啊啊啊,真是抱歉。不說這個了,我帶你去旅館吧。」
「謝謝你。話說我們還不知道彼此的名字呢。我叫小向,你呢?」
「我叫希爾伯特。其實我是旅館的主人呢。」

Problem Source

Problem Set / Description by Paupière

Subtasks

No. Testdata Range Score
1 0~4 16
2 5~9 20
3 10~14 28
4 15~19 36

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 2
6 1000 65536 262144 2
7 1000 65536 262144 2
8 1000 65536 262144 2
9 1000 65536 262144 2
10 1000 65536 262144 3
11 1000 65536 262144 3
12 1000 65536 262144 3
13 1000 65536 262144 3
14 1000 65536 262144 3
15 1000 65536 262144 4
16 1000 65536 262144 4
17 1000 65536 262144 4
18 1000 65536 262144 4
19 1000 65536 262144 4