/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
ストーリー
AtCoder社はAtCoderグッズの通販をしている。 高橋社長は売れ残ったグッズをまとめて福袋として販売することにした。 各袋の重さは出来るだけ均等になることが好ましいが、困ったことに、AtCoder社のオフィスには重さを数値で計ることの出来るはかりがなかった。 代わりに天秤を見つけたので、天秤を使って重さの比較をすることで、出来るだけ均等に分割して欲しい。
問題文
N 個のアイテムがある。 各アイテム i の重さ w_i は未知であり、 2つのアイテム集合の重さの総和を比較することの出来る天秤を用いて、以下の操作を繰り返し行う。
天秤の左右の皿にアイテムを好きなだけ乗せる。乗せたアイテムの重さの総和が左と右どちらが大きいか、もしくは等しいかが判明する。
この操作を Q 回繰り返すことにより、出来るだけ重さの総和の等しい D 個の集合にアイテムを分割せよ。
得点
出力した分割における各集合の重さの総和を t_0,t_1,\cdots,t_{D-1}、t の平均を \bar{t}=\frac{1}{D}\sum_{i=0}^{D-1}t_i とすると、その分散は V=\frac{1}{D}\sum_{i=0}^{D-1} (t_i-\bar{t})^2 により求まる。 このとき、1+\mathrm{round}\left(100\times \sqrt{V}\right) の絶対スコアが得られる。 絶対スコアは小さければ小さいほど良い。
各テストケース毎に、絶対スコアの小さい順での順位に応じた順位スコアが得られ、その和が提出の得点となる。 順位スコアは以下のように計算され、高ければ高いほど良い。
コンテストの提出者数を n_{submit}、自身より小さい絶対スコアを獲得した参加者の人数を n_{lose}、自身と等しい絶対スコアを獲得した他の参加者の人数を n_{tie} とする。この時、このテストケースにおける順位は r=n_{lose}+0.5 n_{tie} と定まり、順位スコアは \mathrm{round}(10^9\times (1-\frac{r}{n_{submit}})) となる。
最終順位はコンテスト終了後に実施されるより多くの入力に対するシステムテストにおける得点で決定される。 暫定テスト、システムテストともに、不正な出力や制限時間超過をした場合、そのテストケースの順位スコアのみ0点となる。 システムテストは CE 以外の結果を得た一番最後の提出に対してのみ行われるため、最終的に提出する解答を間違えないよう注意せよ。
テストケース数
- 暫定テスト: 100個
- システムテスト: 5000個、コンテスト終了後に seeds.txt (sha256=8a39261299bef0387172c0e0c4523c49b0cb993efd4f702ec7cf5124cf5b4c55) を公開
相対評価システムについて
暫定テスト、システムテストともに、CE 以外の結果を得た一番最後の提出のみが順位表に反映される。
順位表に表示されているスコアは相対評価スコアであり、新規提出があるたびに、相対評価スコアが再計算される。 一方、提出一覧から確認出来る各提出のスコアは各テストケース毎の絶対スコアをそのまま足し合わせたものであり、相対評価スコアは表示されない。 最新以外の提出の、現在の順位表における相対評価スコアを知るためには、再提出が必要である。 不正な出力や制限時間超過をした場合、提出一覧から確認出来るスコアは0となるが、順位表には正解したテストケースに対する順位スコアの和が表示されている。
実行時間について
実行時間には多少のブレが生じます。 また、システムテストでは同時に大量の実行を行うため、暫定テストに比べて数%程度実行時間が伸びる現象が確認されています。 そのため、実行時間制限ギリギリの提出がシステムテストでTLEとなる可能性があります。 プログラム内で時間を計測して処理を打ち切るか、実行時間に余裕を持たせるようお願いします。
入出力
まずはじめに、標準入力からアイテム数 N、分割数 D、クエリ回数 Q が以下の形式で与えられる。
N D Q
各値はそれぞれ以下の制約を満たす。
- 30\leq N\leq 100
- 2\leq D\leq N/4
- 2N\leq Q\leq 32N
上記の情報を読み込んだら、以下のクエリを Q 回繰り返す。
q (0\leq q\leq Q-1) 回目のクエリではまず、天秤の左側に乗せるアイテム集合 L と右側に乗せるアイテム集合 R を選択する。 それぞれ空集合であってはならず、また共通部分 L\cap R は空でなければならない。 L と R のどちらにも含まれないアイテムがあっても良い。 n_L=|L|、n_R=|R|、L=\{l_0,\cdots,l_{n_L-1}\}、R=\{r_0,\cdots,r_{n_R-1}\} (0\leq l_i,r_i\leq N-1) としたとき、以下の形式で一行で標準出力に出力せよ。
n_L n_R l_0 \cdots l_{n_L-1} r_0 \cdots r_{n_R-1}
出力の後には改行をし、更に標準出力を flush しなければならない。 そうしない場合、TLEとなる可能性がある。
出力を行うと、天秤がどちら側に傾いたかの情報が標準入力から一行で与えられる。 与えられる文字列は以下の3通りのいずれかである。
<: L の重さの総和は R の重さの総和より小さい。>: L の重さの総和は R の重さの総和より大きい。=: L の重さの総和は R の重さの総和と等しい。
クエリは必ず Q 回行う必要がある。 Q 回のクエリ処理が完了後、出来るだけ重さの総和の等しい D 個の集合にアイテムを分割せよ。 i (0\leq i\leq N-1) 番目のアイテムを d_i (0\leq d_i\leq D-1) 番目の集合に含めるとした時、以下の形式で一行で標準出力に出力せよ。
d_0 \cdots d_{N-1}
例
| q | Output | Input |
|---|---|---|
| 事前情報 | 31 2 128 |
|
| 0 | 2 1 6 22 11 |
> |
| 1 | 2 2 11 22 0 1 |
< |
| \vdots | ||
| 127 | 1 1 14 24 |
< |
| 分割 | 0 0 0 0 0 0 1 1 1 0 1 1 1 0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 1 0 |
入力生成方法
L 以上 U 以下の整数値を一様ランダムに生成する関数を \mathrm{rand\_int}(L,U)、 L 以上 U 未満の実数値を一様ランダムに生成する関数を \mathrm{rand\_double}(L,U) で表す。
アイテム数 N は \mathrm{rand\_int}(30,100) により生成される。 分割数 D は \mathrm{rand\_int}(2,\mathrm{floor}(N/4)) により生成される。 クエリ回数 Q は \mathrm{round}(N\times 2^{\mathrm{rand\_double(1,5)}}) により生成される。
各アイテム i についてそれぞれ独立に、\lambda=10^{-5} の指数分布から値 w'_i を生成し、アイテム i の重みを w_i=\max(1, \mathrm{round}(w'_i)) と設定する。ただし、生成した値 w'_i が \frac{10^5 N}{D} を越えた場合は、再度その値を生成し直す。
ツール(入力ジェネレータ・ローカルテスタ・ビジュアライザ)
- Web版: ローカル版より高性能でアニメーション表示が可能です。
- ローカル版: 使用するにはRust言語のコンパイル環境をご用意下さい。
- Windows用のコンパイル済みバイナリ: Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。
コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。
ツールで用いられる入出力ファイルの仕様
ローカルテスタに与える入力ファイルは以下の形式を用いている。
N D Q
w_0 \cdots w_{N-1}
最後の w_0 \cdots w_{N-1} は各アイテムの重さであり、解答プログラムには与えられない。
ローカルテスタは解答プログラムの出力をそのまま出力ファイルに書き出す。
解答プログラムは、# から始まるコメント行を出力に含めても良い。 Web版ビジュアライザを使用すると、コメント行を対応するタイミングで表示出来るため、デバッグや考察等に役立てることが出来る。 ジャッジプログラムはコメント行を全て無視するため、コメント行を出力するプログラムをそのまま提出可能である。
また、#c から始まるコメント行は特別扱いされ、以下の形式で出力することにより、その時点での暫定的な解をビジュアライザに通知することが出来る。
#c d_0 \cdots d_{N-1}
Story
AtCoder offers online shopping for official goods. CEO Takahashi decided to sell the unsold goods together as a grab bag. The weight of each bag should be as even as possible, but unfortunately, there was no scale in AtCoder's office to measure weight numerically. As an alternative, he found a balance. By using the balance to compare the weights, please divide the goods as evenly as possible.
Problem Statement
There are N items. The weight w_i of each item i is unknown. Using a balance that can compare the sum of the weights of two item sets, you repeat the following operations.
Place as many items as you like on the left and right plates of the balance. Then you can see which side has the greater weight or they have equal weights.
After repeating this operation Q times, divide the items into D sets of equal total weight as much as possible.
Scoring
Let t_0,t_1,\cdots,t_{D-1} be the total weight of items in each set in the output division. Let the mean of t be \bar{t}=\frac{1}{D}\sum_{i=0}^{D-1}t_i. The variance is V=\frac{1}{D}\sum_{i=0}^{D-1} (t_i-\bar{t})^2. Then you will obtain an absolute score of 1+\mathrm{round}\left(100\times \sqrt{V}\right). The lower the absolute score, the better.
For each test case, you will obtain a rank score according to your rank determined by lower absolute score. The score of the submission is the total rank score for each test case. The rank score is calculated as follows, and the higher the rank score, the better.
Let n_{submit} be the number of contestants with submissions, n_{lose} be the number of contestants who received an absolute score lower than yours, and n_{tie} be the number of other contestants who received an absolute score equal to yours. Then your rank in this test case is determined as r=n_{lose}+0.5 n_{tie}, and your rank score is \mathrm{round}(10^9\times (1-\frac{r}{n_{submit}})).
The final ranking will be determined by the system test with more inputs which will be run after the contest is over. In both the provisional/system test, if your submission produces illegal output or exceeds the time limit for some test cases, only the rank score for those test cases will be zero. The system test will be performed only for the last submission which received a result other than CE . Be careful not to make a mistake in the final submission.
Number of test cases
- Provisional test: 100
- System test: 5000. We will publish seeds.txt (sha256=8a39261299bef0387172c0e0c4523c49b0cb993efd4f702ec7cf5124cf5b4c55) after the contest is over.
About relative evaluation system
In both the provisional/system test, the standings will be calculated using only the last submission which received a result other than CE.
The scores shown in the standings are relative, and whenever a new submission arrives, all relative scores are recalculated. On the other hand, the score for each submission shown on the submissions page is the sum of the absolute score for each test case, and the relative scores are not shown. In order to know the relative score of submission other than the latest one in the current standings, you need to resubmit it. If your submission produces illegal output or exceeds the time limit for some test cases, the score shown on the submissions page will be 0, but the standings show the sum of the relative scores for the test cases that were answered correctly.
About execution time
Execution time may vary slightly from run to run. In addition, since system tests simultaneously perform a large number of executions, it has been observed that execution time increases by several percent compared to provisional tests. For these reasons, submissions that are very close to the time limit may result in TLE in the system test. Please measure the execution time in your program to terminate the process, or have enough margin in the execution time.
Input and Output
First, the number of items N, the number of divisions D, and the number of queries Q are given from Standard Input in the following format.
N D Q
Each value satisfies the following constraints.
- 30\leq N\leq 100
- 2\leq D\leq N/4
- 2N\leq Q\leq 32N
After reading the above information, repeat the following query Q times.
In the q-th query (0\leq q\leq Q-1), you select the set of items L to be placed on the left side of the balance and the set of items R to be placed on the right side of the balance. Each set must not be empty, and the common part L\cap R must be empty. There may be items that are not contained in either L or R. Let n_L=|L|, n_R=|R|, L=\{l_0,\cdots,l_{n_L-1}\}, and R=\{r_0,\cdots,r_{n_R-1}\} (0\leq l_i,r_i\leq N-1). Then output to Standard Output on a single line in the following format.
n_L n_R l_0 \cdots l_{n_L-1} r_0 \cdots r_{n_R-1}
The output must be followed by a new line, and you have to flush Standard Output. Otherwise, the submission might be judged as TLE.
After output, the information on which side the balance is tilted is given in a single line from the standard input. The given string is one of the following three cases.
<: The total weight of L is less than the total weight of R.>: The total weight of L is greater than the total weight of R.=: The total weight of L is equal to the total weight of R.
The query must be performed exactly Q times. After Q queries, divide the items into D sets of equal total weight as much as possible. Let i-th (0\leq i\leq N-1) item be included in d_i-th (0\leq d_i\leq D-1) set. Then output to Standard Output on a single line in the following format.
d_0 \cdots d_{N-1}
Example
| q | Output | Input |
|---|---|---|
| Prior information | 31 2 128 |
|
| 0 | 2 1 6 22 11 |
> |
| 1 | 2 2 11 22 0 1 |
< |
| \vdots | ||
| 127 | 1 1 14 24 |
< |
| Division | 0 0 0 0 0 0 1 1 1 0 1 1 1 0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 1 0 |
Input Generation
Let \mathrm{rand\_int}(L,U) be a function that generates a uniform random integer between L and U, inclusive. Let \mathrm{rand\_double}(L,U) be a function that generates a uniform random real number at least L and less than U.
The number of items N is generated by \mathrm{rand\_int}(30,100). The number of divisions D is generated by \mathrm{rand\_int}(2,\mathrm{floor}(N/4)). The number of queries Q is generated by \mathrm{round}(N\times 2^{\mathrm{rand\_double(1,5)}}).
For each item i, we independently generate a value w'_i from the exponential distribution with \lambda=10^{-5}, and we set the weight of item i by w_i=\max(1, \mathrm{round}(w'_i)). If the generated value w'_i exceeds \frac{10^5 N}{D}, we regenerate it.
Tools (Input generator, local tester and visualizer)
- Web version: This is more powerful than the local version providing animations.
- Local version: You need a compilation environment of Rust language.
- Pre-compiled binary for Windows: If you are not familiar with the Rust language environment, please use this instead.
Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited.
Specification of input/output files used by the tools
Input files given to the local tester have the following format.
N D Q
w_0 \cdots w_{N-1}
The last w_0 \cdots w_{N-1} is the weight of each item and is not given to the solution program.
The local tester writes outputs from your program directly to the output file.
Your program may output comment lines starting with #. The web version of the visualizer displays the comment lines with the corresponding query, which may be useful for debugging and analysis. Since the judge program ignores all comment lines, you can submit a program that outputs comment lines as is.
In addition, comment lines starting with #c are treated specially and you can provide the visualizer with a tentative division by outputting in the following format.
#c d_0 \cdots d_{N-1}