Submission #59403729

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
"""
<方針>
- 毎回 `A` の配列を捜査してその数値が出たかどうかを確認すると， `O(N^2)` より `TLE` する．
- 今まででた値を `O(1)` で確認できる方法があれば良い．
  - `list` を使うと， `A` が大きすぎて `MLE` の方向で良くない．
- `dict` を使い， `key` を `A` の値とし， `value` を前回値が出た時の位置とすれば良い．
- すると，全体では `O(N)` となって間に合う．
"""
# 入力
N = int(input())
A = list(map(int, input().split()))
# 答え
ans = []
# 値が出たかどうかのdict
dic = dict()
# 位置と値を取得
for i, a in enumerate(A):
  # 値が既に発見されてる時
  if(a in dic):
    # 前回の位置を取得
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

"""
<方針>
- 毎回 `A` の配列を捜査してその数値が出たかどうかを確認すると， `O(N^2)` より `TLE` する．
- 今まででた値を `O(1)` で確認できる方法があれば良い．
  - `list` を使うと， `A` が大きすぎて `MLE` の方向で良くない．
- `dict` を使い， `key` を `A` の値とし， `value` を前回値が出た時の位置とすれば良い．
- すると，全体では `O(N)` となって間に合う．
"""
# 入力
N = int(input())
A = list(map(int, input().split()))

# 答え
ans = []
# 値が出たかどうかのdict
dic = dict()
# 位置と値を取得
for i, a in enumerate(A):
  # 値が既に発見されてる時
  if(a in dic):
    # 前回の位置を取得
    past = dic[a]
    # 位置を0-indexedを考慮して出力
    ans.append(past+1)
    # 位置を記録
    dic[a] = i
  # 値がまだ発見されてない時
  else:
    # 答えを-1とする．
    ans.append(-1)
    # 位置を記録
    dic[a] = i

# 出力
print(*ans)

Submission Info

Judge Result