ABC142 C go to school TLEが出てしまう理由がわからない

Question

前提・実現したいこと

競技プログラミングの質問です。

atcoder beginner contest 142 C Go To Schoolを解いております。
問題はこちら

まずこちらのソースコードで提出をしたところ、TLEが出てしまいました。 (数字の小さいケースについてはACが出ています)

n = int(input())
A = list(map(int, input().split()))
 
for i in range(1,n+1):
  print(A.index(i) + 1) 

次に、他の方の提出を参考にしてこちらのソースコードで提出したところ、ACが出ました。

n = int(input())
a = list(map(int, input().split()))
 
for i in range(n):
  a[i] = [a[i], i+1]
 
a.sort()
 
for i in range(n):
  print(a[i][1]) 

なぜ前者のコードではTLEで、後者は通るのかがわかりません。
最大計算量としては前者が10^5で後者が10^5*2ではないかと考えており、この考えが正しければ、むしろ後者の方が時間がかかるのでは・・・と思っております。

なぜこのような結果になるのか教えていただきたいです。

程度の低い質問でしたら申し訳ございません。
また、質問に必要な情報等に不足があれば、お手数ですがご指摘いただければ、追記いたします。

よろしくお願いいたします。

Answer 1

最大計算量としては前者が10^5で後者が10^5*2ではないかと考えており、この考えが正しければ

正しくありません。

前者については、list.indexがリニアサーチですので、配列の長さに比例した時間がかかります（外側のループと合わせてO(N**2)）。

後者は、ソートアルゴリズムとして良いものを用いればO(N log N)です。

Comments

[takuma1229]

返信遅れて申し訳ございません。
なるほど！確かにlist.indexでも探索を行ってますね。。。

すごく分かりやすかったです。ありがとうございます！