19454번 - Almost Longest Increasing Subsequence 다국어인터랙티브

Suppose you are given a permutation $a$ of $n$ numbers from $1$ to $n$. In a usual task you would have to find its {\it longest increasing subsequence}: indices $i_1$, $\ldots$, $i_k$ such that $i_1 < \ldots < i_k$ and $a_{i_1} < \ldots < a_{i_k}$, where $k$ is maximum possible.

However, this time the task is different: the numbers are given online, so you must decide whether you take the number or not before you receive the next number. You also know that the input permutation is random, that is, selected uniformly at random from the set of all $n!$ possible permutations. Under these requirements it is impossible to surely find the longest increasing subsequence, but you have to just do good enough. Formally, let $k$ be the length of the longest increasing subsequence of the given permutation. Then, finding any increasing subsequence of length at least $0.65k$ will suffice.

First, interactor sends a single number $n$ ($n = 10^5$) which is the length of the permutation. Next, interactor sends $n$ numbers one by one, each on a separate line. After receiving each number you should print one integer to the standard output, which is $1$ if you take the given number and $0$ otherwise.

The sequence given is a permutation of $1$, $\ldots$, $n$: all elements are distinct and each of then is from $1$ to $n$.

Every number selected by participant (except for the first one) should be greater than the previous one.

In the sample case $n = 5$. Any solution which follows the output format passes this testcase.

The sample test is used only to illustrate the interaction format and is not included in the testset. Each test from the testset has $n = 10^5$.

In this problem, technically, a random permutation is an array of $1$, $\ldots$, $n$ shuffled with some pseudo-random number generator.