시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB1000.000%

문제

Note: in the following statement, $\overline{b_1 \dots b_k}$ represents an integer written out in binary notation, where $b_1$ is the most significant bit, and $b_k$ is the least significant bit.

Roxanne the space witch, while riding her broomstick throughout the galaxy, came across a planet in which everybody danced a strange dance: planet Br-perm. In this dance, the participants stand in a line, and then reorder themselves. Suppose $2^k$ people are dancing. Then, the person at position $\overline{b_1 \dots b_k}$ goes to position $\overline{b_1 \dots b_k}$ (indexed from $0$).

Roxanne noticed also that every person on Br-perm wears one of $26$ colors of clothing. These colors are represented by the letters of the Latin alphabet.

The Br-perm-ians place special significance on rows of dancers where the sequence of colors of clothing that people are wearing before and after the dance are the same. They call such sequences nice. For instance, when $k = 2$, we have a row of four dancers $0, 1, 2, 3$, that after the dance become ordered like so: $0, 2, 1, 3$. So, the sequence of clothing colors abba is nice, but abca is not.

The Br-perm-ians have asked Roxanne to help them with a difficult matter (space witches always seem to have to help people with their problems). They show her a long row of $n$ dancers, and ask her several questions: “is the sequence of length $2^k$ starting at dancer $i$ nice?”

인터랙션 프로토콜

The contestant must implement two functions. The first of them is the following:

void init(int n, const char s[]);

This function will be called exactly once, at the beginning of the interaction, and supplies the contestant with the string of clothing colors of the dancers, through parameter s.

The second function that the contestant must implement is:

int query(int i, int k);

This function will be called exactly $Q$ times and must return $1$ if and only if the contiguous subsequence of s starting at the $i$th dancer (indexed from $0$), and of length $2^k$, is nice. It must return $0$ otherwise. It’s guaranteed that the subsequence will not exceed the end of s.

제한

  • $1 ≤ N ≤ 500\,000$
  • $1 ≤ Q ≤ 500\,000$

서브태스크 1 (13점)

  • $1 ≤ N ≤ 1\,000$
  • $1 ≤ Q ≤ 1\,000$

서브태스크 2 (37점)

  • $1 ≤ N ≤ 100\,000$
  • $1 ≤ Q ≤ 100\,000$

서브태스크 3 (17점)

  • s contains only the characters 'a' and 'b'.
  • The colors are independently randomly chosen with a certain fixed probability for each testcase.

서브태스크 4 (33점)

  • No additional constraints.

예제 입력 1

init(8, "axxyxxyb")

예제 출력 1

query(0, 3) = true
query(1, 1) = true
query(0, 2) = false
query(3, 2) = true

제출할 수 있는 언어

C++17, C++20, C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 예제는 채점하지 않는다.