問題一覧 > ⚠未証明/不備あり問題

No.1743 Permutation Code

レベル : / 実行時間制限 : 1ケース 8.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 0
作問者 : noya2 / テスター : ミドリムシ
お気に入りにしたユーザー ProblemId : 4991 / 自分の提出
問題文最終更新日: 2021-11-21 10:51:58
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

Note

The problem setter has no intended solution for this problem.

We are eagerly waiting for some user to solve it.

Problem Statement

Noya-kun tried to pass down a permutation $P=(P_1,P_2,\dots ,P_N)$ of $(1,2,\dots ,N)$ to the distant future by encrypting it.

The permutation $P$ is encrypted by the following procedure.

  • For every $i$ such that $1\le i\le N$, let $S_i$ be the string obtained by writing $P_i$ in base $2$ without any extra leading $0$.
  • Define the string $C$ by $C=S_1 + S_2 + \dots + S_N$.

  • You are given $C$.

    Output one possibility for the permutation $P$ that Noya-kun tried to pass down, in base $10$, separated by spaces.

    Constraints

  • $1\le |C| \le 983041$ ($|C|=983041$ when $N=2^{16}-1$)
  • $C$ is a string consisting of 0 and 1
  • There exist a positive integer $N$ and a permutation $P=(P_1,P_2,\dots ,P_N)$ of $(1,2,\dots ,N)$ such that encrypting it results in $C$.
  • Input

    $C$
    

    Output

    Output one possibility for the permutation $P$ that Noya-kun tried to pass down, in base $10$, separated by spaces.

    Print a newline at the end.

    Sample

    Sample 1
    Input
    11100101
    Output
    3 4 2 1

    Encrypting $P=(3,4,2,1)$ results in 11100101, so it is one of the candidates.

    In this sample case, there is no answer other than 3 4 2 1.

    Sample 2
    Input
    10100100111000011101101110010111111010010111010110001111100110010001110101
    Output
    20 19 16 14 13 12 11 7 2 18 3 10 1 8 15 9 4 17 6 5

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。