Hide-and-seek(かくれんぼ) - joi2010-day3
時間制限: 1秒
メモリ制限: 64MB
あなたは, JOI社が発売したテレビゲームソフトを手に入れた. なかなか良くできたゲームであり, それなりに楽しみながら毎日プレイしていた.
ある日, ゲーマーの中で「かくれんぼ」と呼称されるステージが出現した. どうやらそのステージにはバグがあり, 優れたゲーマーでさえもほんのわずかな確率でしかクリアできない物であるらしい.
何度もそのステージに挑戦する中であなたは, とても高速な判断を行うことでクリアできる可能性が有ることに気づき, プログラムを作成して対処出来るのではないかと考えた.
かくれんぼステージは, 多数の障害物が配置された場所が舞台となっている. 舞台は長方形で1 × 1 の正方形のマスに分かれており, 各マスは1 ≤ x ≤ 100,000 , 1 ≤ y ≤ 1,000,000,000 を満たす整数x,yによって(x,y)と表現される. (1,1)は左上隅のマスであり, (x+1,y+1)は(1,1)から右にx, 下にy進んだマスを表現する.
各障害物はy座標が同じ連続したw個のマスに置かれる. つまり, 障害物はw × 1個のマスを占める長方形の形に見える. その中のx座標が一番小さいマスの座標(x,y)と, 長さwの組で1つの障害物が表現されている. 障害物は2 ≤ yのマスに配置される. 障害物同士が重なることはない.
ステージが始まるとプレーヤーは舞台を動き回る. プレーヤーは障害物のあるマスを含めた任意のマスに移動できる．
一定の時間が経過すると敵が出現し攻撃を行う. プレーヤーはこの時必ず障害物の中に隠れる必要がある. 障害物の中に隠れるには, 障害物のあるマスに居ればよい. 適切な障害物の中に隠れることでプレーヤーは攻撃を受けずに済み, 敵に反撃するチャンスを得ることが出来る. チャンスを利用することでステージがクリアできる.
敵はM種類の武器（例えば, 拳銃, ライフル, 無反動砲, 電磁投射砲などなど）を所持している. 武器には1からMの固有の番号がつけられており, i番の武器には攻撃力a[i]が設定されている. 攻撃力は, その数値の分だけ障害物を破壊出来ることを表している.
破壊された障害物の中にプレーヤーが隠れている場合, プレーヤーはダメージを受けることになる．
敵はランダムに選ばれたxを使い, (x,1)に出現し, 下方向に向かってランダムに選択した武器を使い攻撃する予定だった. ところが, ゲームのバグによって, 敵は必ずプレーヤーのいるx座標を選択し, プレーヤーに向けて攻撃してしまう事となった.
あなたは自作のプログラムを使い, 敵からどの武器を使って攻撃されても良いように, 武器毎に攻撃を受けずに済む最適な隠れ場所を探すことにした. 攻撃を受けずに済む最適な隠れ場所は, プレーヤーが反撃を行いやすいように, もっともy 座標が小さい所である. また, そのような場所が複数存在する場合には, その中でもっともx座標が小さい所が最適である.
課題(TASK)
障害物の情報と各武器の攻撃力が与えられたとき, 敵が所持する武器毎に最適な隠れ場所を求めるプログラムを作成せよ. ただし, どのように隠れても攻撃を受けてしまう場合には, 隠れる場所がないという意味で(-1,-1)を出力せよ.
図1: 攻撃力が4である武器に対応する隠れ方
制限(CONSTRAINTS)
| 1 ≤ N ≤ 50,000 | 障害物の数 |
| 1 ≤ M ≤ 50,000 | 武器の種類 |
| 1 ≤ x[i] ≤ 100,000 | 障害物iが配置されるマスの中でもっとも小さいx座標 |
| 2 ≤ y[i] ≤ 1,000,000,000 | 障害物iのy座標 |
| 1 ≤ w[i] + x[i] – 1 ≤ 100,000 | w[i]は障害物iの長さ |
| 1 ≤ a[j] ≤ N | 武器jの攻撃力 |
入力(INPUT)
標準入力から以下の入力を読み込め.
- 1行目には整数NとMが空白を区切りとして書かれている.
- 続くN行のうちi行目には整数x[i], y[i], w[i] が空白を区切りとして書かれている.
- 続くM行のうちj行目には整数a[j]が書かれている.
出力(OUTPUT)
標準出力に以下のデータを出力せよ.
- データはM行からなる. j行目は2つの整数x[j]とy[j]が空白区切りで書かれており, j番目の武器に対応する最適な隠れ場所の座標が(x[j],y[j])である事を表す. どのように隠れてもj番目の武器の攻撃を受けてしまう場合はx[j] = y[j] = -1 とせよ.
採点基準(GRADING)
30点分のテストグループにおいて, x[i] + w[i] – 1 ≤ 10,000 かつN ≤ 1,000 である.
入出力例(EXAMPLE)
| 入力例(Sample Input) | 出力例(Sample Output) |
|---|---|
| 13 2 2 2 10 14 3 9 15 6 12 3 7 5 16 8 9 15 10 3 4 13 10 11 11 11 5 4 11 11 14 12 6 9 7 20 4 8 13 5 5 4 7 |
15 10 -1 -1 |
この例は図1 と対応する．攻撃力が7 の場合は隠れる場所が無いため，-1 -1 を出力する．