反省

問題を読んでおらず、必要な実装(解法2)に対して、明らかに重い実装(解法1)をしてしまったので自戒。

題意

問題はとてもシンプルだが、まとめると以下の通り。

n階建ての建物があり、すべての階にはレストランがある。
あなたのオフィスはs階にある。
ところが、k個の階でレストランが工事中である。
一番近い回転中のレストランとは何フロア離れているか？
※1: k <= 1000

In/Outの例を見ると、

n,s,k = 100 76 8
kの配列 76 75 36 67 41 74 10 77

100階建ての建物があり、オフィスは76階であり、工事中の階は(sortして) 10 36 41 67 74 75 76(オフィス) 77 。
オフィスの上の階で一番近いのは78階、下で近いのは73階になるので、78階に向かえばよく、2が答えになる。

解法1: ソート済みの配列を前後に探索

単純に上記で述べた実装をする。以下の図がイメージ。

1. kの配列をソートし、sの位置を知る。
 　　尚、sが存在しない場合、答えは`0`(移動しなくていい)である。)
2. 配列を左方向に見る。差が1である限り左に進んでいく。
3. 差が1よりも大きい場合、その間のレストランはすべて開いているので、一番sに近い階が下に降りた場合に最も近いレストランである。
　　（図では76から下り、74の次は67であるため、68-73階のレストランは空いている）
4. 2,3において、下に降りても開いているレストランが存在しないことがある。
　　(例えば、2階にオフィスがあり、1,2階のレストランが閉まっている場合、下に答えはない)
5. 上記を同様に右方向（上側）にも探索する
6. 上にも下にも候補となるレストランがあるならminをとり、片方がしか候補がないならそれを答えとする

これを実装したものが以下。

q = int(input())
for qq in range(q):
    res = -1
    n, s, k = map(int, input().split())
    dat = list(map(int, input().split()))
    dat = list(set(dat)) # 題意的にある階がリストに複数回含まれる時の対策 [2,2,3]等
    dat.sort()
    if s not in dat: # もし、sがリストにないなら、sの階のレストランは開いている
        print(0)
        continue
    ind = dat.index(s) # sの入っているインデックスを取得
    r = l = -1 # 下方向(l)も上方向(r)も見つかっていないことにする
    # 上方向の探索
    for i in range(ind + 1, len(dat)): # sの一つ上のインデックスから最上階まで探索
        if (dat[i] - dat[i - 1]) != 1: # もし、差が1出ないなら
            r = dat[i - 1] + 1 # 上向きはその区間の一番低い階が候補
            break
    if r == -1 and dat[-1] != n: # もし、連続した階しかなく、しかし、リストの最後が最上階でないなら
        r = dat[-1] + 1 # リストの一番上の階の上が候補となる

    # 同様の処理を下方向にも行う
    for i in range(ind - 1, -1, -1):
        if (dat[i + 1] - dat[i]) != 1:
            l = dat[i + 1] - 1
            break
    if l == -1 and dat[0] != 1:
        l = dat[0] - 1
        
    if r == l == -1: # 題意より開いているレストランがないことはない()
        print("ERROR")
    elif r == -1: # 上方向に候補がないなら
        print(s - l) # 答えは下方向
    elif l == -1: # 下方向に候補がないなら
        print(r - s)
    else: # 上も下も候補があるなら差が小さいほう
        print(min(s - l, r - s))

解法2: ソートもせずに単にリストを探索する

この問題の説明に書いたが、そもそもこの問題でレストランが閉じているリストの最大値は1000である(※1の通り)。
このため、sを中心に500階分リストに存在するか確認すればよい。

1000要素のリストに対する500回程度の探索なので、ソート＆二分探索もいらない。ということで、以下でAC。

q = int(input())
for qq in range(q):
    n, s, k = map(int, input().split())
    dat = list(map(int, input().split()))
    res = 0 # オフィスの位置からのdelta
    while True:
        if (s + res) not in dat and (s + res) <= n: break # 上方向
        if (s - res) not in dat and (s - res) >= 1: break # 下方向
        res += 1
    print(res)