Problem:


Score : 800 points

Problem Statement

There are N rabbits on a number line.
The rabbits are conveniently numbered 1 through N.
The coordinate of the initial position of rabbit i is x_i.

The rabbits will now take exercise on the number line, by performing sets described below.
A set consists of M jumps. The j-th jump of a set is performed by rabbit a_j (2≤a_j≤N-1).
For this jump, either rabbit a_j-1 or rabbit a_j+1 is chosen with equal probability (let the chosen rabbit be rabbit x), then rabbit a_j will jump to the symmetric point of its current position with respect to rabbit x.

The rabbits will perform K sets in succession.
For each rabbit, find the expected value of the coordinate of its eventual position after K sets are performed.

Constraints

3≤N≤10^5

x_i is an integer.

|x_i|≤10^9

1≤M≤10^5

2≤a_j≤N-1

1≤K≤10^{18}

Input

The input is given from Standard Input in the following format:

N
x_1 x_2 ... x_N
M K
a_1 a_2 ... a_M

Output

Print N lines.
The i-th line should contain the expected value of the coordinate of the eventual position of rabbit i after K sets are performed.
The output is considered correct if the absolute or relative error is at most 10^{-9}.

Sample Input 1

3
-1 0 2
1 1
2

Sample Output 1

-1.0
1.0
2.0

Rabbit 2 will perform the jump.
If rabbit 1 is chosen, the coordinate of the destination will be -2.
If rabbit 3 is chosen, the coordinate of the destination will be 4.
Thus, the expected value of the coordinate of the eventual position of rabbit 2 is 0.5×(-2)+0.5×4=1.0.

Sample Input 2

3
1 -1 1
2 2
2 2

Sample Output 2

1.0
-1.0
1.0

x_i may not be distinct.

Sample Input 3

5
0 1 3 6 10
3 10
2 3 4

Sample Output 3

0.0
3.0
7.0
8.0
10.0



Sample input:
3
-1 0 2
1 1
2


Sample output:
-1.0
1.0
2.0

Submission status: Wrong Answer

Solution code:
import copy
n = int(input())
x = list(map(int,input().split()))
m,k = map(int,input().split())
a = list(map(int,input().split()))
b = copy.deepcopy(x)
kako = [x]
sira = set(a)
sira = list(sira)
while True:
  for i in range(m):
    to = a[i]-1
    if to == 0:
      b[0] = b[1]*2-b[0]
    elif to == n-1:
      b[n-1] = b[n-2]*2 - b[n-1]
    else:
      b[to] = (b[to+1]*2-b[to]+b[to-1]*2-b[to])/2
  for i in a:
    if b[i] != x[i]:
      break
  else:
    break
  kako.append(copy.deepcopy(b))
k %= len(kako)
for i in kako[k]:
  print(i)

Submission status: Wrong Answer

Solution code:
from math import log

n = int(raw_input())
x = map(int, raw_input().split())
m, k = map(int, raw_input().split())
a = map(lambda x:int(x) - 2, raw_input().split())

logk = log(k, 2)
dy = [x[i + 1] - x[i] for i in xrange(n - 1)]
swap = [range(n - 1) for _ in xrange(int(logk + 1))]

for i in xrange(m):
    swap[0][a[i]], swap[0][a[i] + 1] = swap[0][a[i] + 1], swap[0][a[i]]

j = 1
while j <= logk:
    tmpswap = [None] * (n - 1)
    for i in xrange(n - 1):
        tmpswap[i] = swap[j - 1][swap[j - 1][i]]
    for i in xrange(n - 1):
        swap[j][i] = tmpswap[i]
    j += 1

j = 0
while k >> j > 0:
    if (k >> j) & 1 == 1:
        tmp = [None] * (n -1)
        for i in xrange(n - 1):
            tmp[swap[j][i]] = dy[i]
        dy = tmp
    j += 1

ans = x[0]
print(ans)
for i in xrange(n - 1):
    ans += dy[i]
    print(ans)

Submission status: Wrong Answer

Solution code:
from math import log

n = int(raw_input())
x = map(int, raw_input().split())
m, k = map(int, raw_input().split())
a = map(lambda x:int(x) - 2, raw_input().split())

logk = log(k, 2)
dy = [x[i + 1] - x[i] for i in xrange(n - 1)]
swap = [range(n - 1) for _ in xrange(int(logk + 1))]

for i in xrange(m):
    swap[0][a[i]], swap[0][a[i] + 1] = swap[0][a[i] + 1], swap[0][a[i]]

j = 1
while j <= logk:
    tmpswap = [None] * (n - 1)
    for i in xrange(n - 2):
        tmpswap[i], tmpswap[i + 1] = swap[j - 1][swap[0][i]], swap[j - 1][swap[0][i + 1]]
    for i in xrange(n - 1):
        swap[j][i] = tmpswap[i]
    j += 1

j = 0
while k >> j > 0:
    if (k >> j) & 1 == 1:
        tmp = [None] * (n -1)
        for i in xrange(n - 1):
            tmp[swap[j][i]] = dy[i]
        dy = tmp
    j += 1

ans = x[0]
print(ans)
for i in xrange(n - 1):
    ans += dy[i]
    print(ans)

Submission status: Wrong Answer

Solution code:
from math import log

n = int(raw_input())
x = map(int, raw_input().split())
m, k = map(int, raw_input().split())
a = map(lambda x:int(x) - 2, raw_input().split())

logk = log(k, 2)
dy = [x[i + 1] - x[i] for i in xrange(n - 1)]
swap = [range(n - 1) for _ in xrange(int(logk + 1))]

for i in xrange(m):
    swap[0][a[i]], swap[0][a[i] + 1] = swap[0][a[i] + 1], swap[0][a[i]]

j = 1
while j <= logk:
    for i in xrange(n - 2):
        swap[j][i], swap[j][i + 1] = swap[j - 1][swap[0][i]], swap[j - 1][swap[0][i + 1]]
    j += 1

j = 0
while k >> j > 0:
    if (k >> j) & 1 == 1:
        tmp = [None] * (n -1)
        for i in xrange(n - 1):
            tmp[swap[j][i]] = dy[i]
        dy = tmp
    j += 1

ans = x[0]
print(ans)
for i in xrange(n - 1):
    ans += dy[i]
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = list(map(int, input().split()))
m, k = map(int, input().split())
t = [i for i in range(n)] # 置換
e = [i for i in range(n)]
d = [x[i + 1] - x[i] if i < n - 1 else n - 1 for i in range(n)] # 置換の対象
a = list(map(int, input().split()))

for i in a:
    # 一回分の置換を行う
    t[i - 2], t[i - 1] = t[i - 1], t[i - 2]

def mul(p, q):
    tmp = [p[q[i]] for i in range(n)]
    return tmp

# 繰り返し二乗法
while k:
    if k & 1:
        e = mul(e, t)
        break
    t = mul(t, t)
    k >>= 1

ans  = x[0]
for i in range(n):
    print(ans)
    ans += d[e[i]]

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(raw_input())
x_vec = np.array([0] + map(int, raw_input().split()), dtype='double')
M, K = map(int, raw_input().split())
a_list = map(int, raw_input().split())
 
for k in range(10):
    for a in a_list:
        x_vec[a] = x_vec[a-1] + x_vec[a+1] - x_vec[a]

for i in range(1, N+1):
    print x_vec[i]

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(raw_input())
x_vec = np.array([0] + map(int, raw_input().split()), dtype='double')
M, K = map(int, raw_input().split())
a_list = map(int, raw_input().split())


y_vec = x_vec.copy()
for a in a_list:
    y_vec[a] = y_vec[a-1] + y_vec[a+1] - y_vec[a]
if np.array_equal(x_vec, y_vec):
    pass
else:
    x_vec = y_vec

for i in range(1, N+1):
    print y_vec[i]

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(raw_input())
x_vec = np.array([0] + map(int, raw_input().split()), dtype='double')
M, K = map(int, raw_input().split())
a_list = map(int, raw_input().split())


y_vec = x_vec.copy()
for a in a_list:
    y_vec[a] = y_vec[a-1] + y_vec[a+1] - y_vec[a]
#if np.array_equal(x_vec, y_vec):
#    break
#else:
#    x_vec = y_vec

for i in range(1, N+1):
    print y_vec[i]

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(raw_input())
x_vec = np.array([0] + map(int, raw_input().split()), dtype='double')
M, K = map(int, raw_input().split())
a_list = map(int, raw_input().split())


y_vec = x_vec.copy()
for a in a_list:
    y_vec[a] = y_vec[a-1] + y_vec[a+1] - y_vec[a]
x_vec = y_vec

for i in range(1, N+1):
    print y_vec[i]

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(raw_input())
x_vec = np.array([0] + map(int, raw_input().split()), dtype='double')
M, K = map(int, raw_input().split())
a_list = map(int, raw_input().split())

print 0

Submission status: Wrong Answer

Solution code:
N = input()
X = map(float,raw_input().split())
M,K = map(int,raw_input().split())
A = map(int,raw_input().split())

FLG = False

for i in xrange(K):
    _X = list(X)
    for i in xrange(M):
        _X[A[i]-1] = _X[A[i]-2]+_X[A[i]]-_X[A[i]-1]
    for i in xrange(N):
        diff = abs(X[i]-_X[i])
        flg = True
        if diff == 0:
            break
        elif diff > 10**(-10) and diff/X[i] > 10**(-10):
            FLG = False
            flg = False
            break
    if flg:
        if FLG:
            break
        else:
            FLG = True
    X = _X
for i in _X:
    print i

Submission status: Wrong Answer

Solution code:
N = input()
X = map(float,raw_input().split())
M,K = map(int,raw_input().split())
A = map(int,raw_input().split())

FLG = False

for i in xrange(K):
    _X = list(X)
    for i in xrange(M):
        _X[A[i]-1] = _X[A[i]-2]+_X[A[i]]-_X[A[i]-1]
    for i in xrange(N):
        diff = abs(X[i]-_X[i])
        flg = True
        if diff == 0:
            break
        elif diff > 10**(-9) and diff/X[i] > 10**(-9):
            FLG = False
            flg = False
            break
    if flg:
        if FLG:
            break
        else:
            FLG = True
    X = _X
for i in _X:
    print i

Submission status: Wrong Answer

Solution code:
N = int(input())
X = list(map(int, input().split()))
M, K = map(int, input().split())
A = list(map(int, input().split()))

K = K % M + 1

arr = [X[:]]
for k in range(K):
    for a in A:
        temp = []
        for ar in arr:
            tmp1 = ar[:]
            tmp1[a - 1] = tmp1[a - 2] * 2 - tmp1[a - 1]
            temp.append(tmp1)
            tmp2 = ar[:]
            tmp2[a - 1] = tmp2[a] * 2 - tmp2[a - 1]
            temp.append(tmp2)
        arr = temp
    ans = [0 for i in range(N)]
    L = len(arr)
    for ar in arr:
        for i in range(N):
            ans[i] += ar[i] / L
    arr = [ans]
for ar in arr[0]:
    print(ar)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
xs = np.array(list(map(int, input().split())), dtype=np.int64)
M, K = map(int, input().split())
ids = np.array(list(map(int, input().split()))) - 1

s = set()
l = []
for j in range(K):
    for i in ids:
        xs[i] = xs[i-1:i+2].sum() - xs[i]*2
    sxs = str(xs)
    if str(xs) in s:
        break
    else:
        s.update([sxs])
        l.append(np.array(xs))

print("\n".join(map(str, l[K%len(s)-1])))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
x = list(map(int, input().split()))
M, K = map(int, input().split())
a = [ai - 1 for ai in map(int, input().split())]
his = [tuple(x)]
s = {tuple(x)}
for _ in range(K):
    for i in a:
        x[i] = x[i - 1] + x[i + 1] - x[i]
    if tuple(x) in s:
        break
    s.add(tuple(x))
    his.append(tuple(x))
for xi in his[K % len(his)]:
    print(xi)

Submission status: Time Limit Exceeded

Solution code:
import copy
n = int(input())
x = list(map(int,input().split()))
m,k = map(int,input().split())
a = list(map(int,input().split()))
b = copy.deepcopy(x)
kako = [x]
while True:
  for i in range(m):
    to = a[i]-1
    if to == 0:
      b[0] = b[1]*2-b[0]
    elif to == n-1:
      b[n-1] = b[n-2]*2 - b[n-1]
    else:
      b[to] = (b[to+1]*2-b[to]+b[to-1]*2-b[to])/2
  if b in kako:
    break
  kako.append(copy.deepcopy(b))
rp = kako.index(b)
if rp>= k:
  for i in kako[k]:
    print(i)
  exit()
k -= rp
kako = kako[rp:]
k %= len(kako)
for i in kako[k]:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
import copy
n = int(input())
x = list(map(int,input().split()))
m,k = map(int,input().split())
a = list(map(int,input().split()))
b = copy.deepcopy(x)
kako = [x]
while True:
  for i in range(m):
    to = a[i]-1
    if to == 0:
      b[0] = b[1]*2-b[0]
    elif to == n-1:
      b[n-1] = b[n-2]*2 - b[n-1]
    else:
      b[to] = (b[to+1]*2-b[to]+b[to-1]*2-b[to])/2
  if b ==x:
    break
  kako.append(copy.deepcopy(b))
k %= len(kako)
for i in kako[k]:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
n=input()
X=map(int,raw_input().split())
m,k=map(int,raw_input().split())
A=map(int,raw_input().split())
X0=X[:]
def s():
    for a in A:X[a-1]=X[a-2]+X[a]-X[a-1]
i=1
s()
while i<k and X0!=X:
    s()
    i+=1
if i!=k:
    k%=i
    while k:
        k-=1
        s()
print"\n".join(map(str,X))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(raw_input())
x_vec = np.array([0] + map(int, raw_input().split()), dtype='double')
M, K = map(int, raw_input().split())
a_list = map(int, raw_input().split())

k = 0
while k < K:
    y_vec = x_vec.copy()
    for a in a_list:
        y_vec[a] = y_vec[a-1] + y_vec[a+1] - y_vec[a]
    if np.array_equal(x_vec, y_vec):
        break
    else:
        x_vec = y_vec.copy()
        k += 1

for i in range(1, N+1):
    print x_vec[i]

Submission status: Time Limit Exceeded

Solution code:
N = input()
X = map(float,raw_input().split())
M,K = map(int,raw_input().split())
A = map(int,raw_input().split())

FLG = False

for i in xrange(K):
    _X = list(X)
    for i in xrange(M):
        _X[A[i]-1] = _X[A[i]-2]+_X[A[i]]-_X[A[i]-1]
    flg = True
    for i in xrange(N):
        diff = abs(X[i]-_X[i])
        if diff != 0:
            flg = False
            break
    if flg:
        FLG = True
        break
    for i in xrange(N):
        diff = abs(X[i]-_X[i])
        flg = True
        if diff == 0 or (diff > 10**(-9) and diff/X[i] > 10**(-9)):
            FLG = False
            flg = False
            break
    if flg:
        if FLG:
            break
        else:
            FLG = True
    X = _X
for i in _X:
    print i

Submission status: Time Limit Exceeded

Solution code:
N = input()
X = map(float,raw_input().split())
M,K = map(int,raw_input().split())
A = map(int,raw_input().split())

FLG = False

for i in xrange(K):
    _X = list(X)
    for i in xrange(M):
        _X[A[i]-1] = _X[A[i]-2]+_X[A[i]]-_X[A[i]-1]
    flg = True
    for i in xrange(N):
        diff = abs(X[i]-_X[i])
        if diff != 0:
            flg = False
            break
    if flg:
        break
    for i in xrange(N):
        diff = abs(X[i]-_X[i])
        flg = True
        if diff == 0 or (diff > 10**(-9) and diff/X[i] > 10**(-9)):
            FLG = False
            flg = False
            break
    if flg:
        if FLG:
            break
        else:
            FLG = True
    X = _X
for i in _X:
    print i

Submission status: Time Limit Exceeded

Solution code:
N = input()
X = map(float,raw_input().split())
M,K = map(int,raw_input().split())
A = map(int,raw_input().split())

FLG = False

for i in xrange(K):
    _X = list(X)
    for i in xrange(M):
        _X[A[i]-1] = _X[A[i]-2]+_X[A[i]]-_X[A[i]-1]
    for i in xrange(N):
        diff = abs(X[i]-_X[i])
        flg = True
        if diff != 0:
            FLG = False
            flg = False
            break
        elif diff > 10**(-9) and diff/X[i] > 10**(-9):
            FLG = False
            flg = False
            break
    if flg:
        if FLG:
            break
        else:
            FLG = True
    X = _X
for i in _X:
    print i

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    N = int(input())
    initialPlace = [int(x) for x in input().split()]
    M, K = [int(x) for x in input().split()]
    jumpList = [int(x) for x in input().split()]

    id = np.identity(N)

    mat1 = np.matrix(id[:])
    for j in range(M):
        matTemp =  np.identity(N)
        matTemp[ jumpList[j]-1 ][ jumpList[j] -2] = 1
        matTemp[ jumpList[j]-1 ][ jumpList[j] -1] = -1
        matTemp[ jumpList[j]-1 ][ jumpList[j] ] = 1

        mat1 = np.matrix(matTemp).dot(mat1)

    placeOut = np.linalg.matrix_power(mat1, K).dot(initialPlace)

    for pos in np.array(placeOut)[0]:
        print (str(pos))

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
x = map(float, raw_input().split())
m, k = map(int, raw_input().split())
a = map(int, raw_input().split())

for i in xrange(k):
    for j in a:
        x[j-1] = x[j-2] - x[j-1] + x[j]

for i in x:
    print i

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

EPS = 1e-9

#http://www.deqnotes.net/acmicpc/2d_geometry/lines
def dot(a, b):
    return a.real * b.real + a.imag * b.imag

def cross(a, b):
    return a.real * b.imag - a.imag * b.real

def distance(a, b, c):
    if dot(b-a, c-a) <= EPS:
        return abs(c-a)
    if dot(a-b, c-b) <= EPS:
        return abs(c-b)
    return abs(cross(b-a, c-a)/(b-a))

N = n()
X = ln()
M, K = ln()
A = ln()

ori = X[:]

for k in xrange(10**3):
#    exp_once = [0] * N
    for a in A:
        cur = a - 1
        prev = a - 2
        next = a
        exp = X[next] - X[cur] + X[prev] - X[cur]
#        exp_once[cur] = exp
        X[cur] += exp
    
    if X == ori:
        loop = k + 1
#        print X
        break
#    print X


for k in xrange(K % loop):
    for a in A:
        cur = a - 1
        prev = a - 2
        next = a
        exp = X[next] - X[cur] + X[prev] - X[cur]
#        exp_once[cur] = exp
        X[cur] += exp

for x in X:
    print float(x)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

EPS = 1e-9

#http://www.deqnotes.net/acmicpc/2d_geometry/lines
def dot(a, b):
    return a.real * b.real + a.imag * b.imag

def cross(a, b):
    return a.real * b.imag - a.imag * b.real

def distance(a, b, c):
    if dot(b-a, c-a) <= EPS:
        return abs(c-a)
    if dot(a-b, c-b) <= EPS:
        return abs(c-b)
    return abs(cross(b-a, c-a)/(b-a))

N = n()
X = ln()
M, K = ln()
A = ln()

ori = X[:]

for k in xrange(10**4):
#    exp_once = [0] * N
    for a in A:
        cur = a - 1
        prev = a - 2
        next = a
        exp = X[next] - X[cur] + X[prev] - X[cur]
#        exp_once[cur] = exp
        X[cur] += exp
    
    if X == ori:
        loop = k + 1
#        print X
        break
#    print X


for k in xrange(K % loop):
    for a in A:
        cur = a - 1
        prev = a - 2
        next = a
        exp = X[next] - X[cur] + X[prev] - X[cur]
#        exp_once[cur] = exp
        X[cur] += exp

for x in X:
    print float(x)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

EPS = 1e-9

#http://www.deqnotes.net/acmicpc/2d_geometry/lines
def dot(a, b):
    return a.real * b.real + a.imag * b.imag

def cross(a, b):
    return a.real * b.imag - a.imag * b.real

def distance(a, b, c):
    if dot(b-a, c-a) <= EPS:
        return abs(c-a)
    if dot(a-b, c-b) <= EPS:
        return abs(c-b)
    return abs(cross(b-a, c-a)/(b-a))

N = n()
X = ln()
M, K = ln()
A = ln()

ori = X[:]

for k in xrange(10**6):
#    exp_once = [0] * N
    for a in A:
        cur = a - 1
        prev = a - 2
        next = a
        exp = X[next] - X[cur] + X[prev] - X[cur]
#        exp_once[cur] = exp
        X[cur] += exp
    
    if X == ori:
        loop = k + 1
#        print X
        break
#    print X


for k in xrange(K % loop):
    for a in A:
        cur = a - 1
        prev = a - 2
        next = a
        exp = X[next] - X[cur] + X[prev] - X[cur]
#        exp_once[cur] = exp
        X[cur] += exp

for x in X:
    print float(x)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

EPS = 1e-9

#http://www.deqnotes.net/acmicpc/2d_geometry/lines
def dot(a, b):
    return a.real * b.real + a.imag * b.imag

def cross(a, b):
    return a.real * b.imag - a.imag * b.real

def distance(a, b, c):
    if dot(b-a, c-a) <= EPS:
        return abs(c-a)
    if dot(a-b, c-b) <= EPS:
        return abs(c-b)
    return abs(cross(b-a, c-a)/(b-a))

N = n()
X = ln()
M, K = ln()
A = ln()

ori = X[:]

for k in xrange(10**7):
#    exp_once = [0] * N
    for a in A:
        cur = a - 1
        prev = a - 2
        next = a
        exp = X[next] - X[cur] + X[prev] - X[cur]
#        exp_once[cur] = exp
        X[cur] += exp
    
    if X == ori:
        loop = k + 1
#        print X
        break
#    print X


for k in xrange(K % loop):
    for a in A:
        cur = a - 1
        prev = a - 2
        next = a
        exp = X[next] - X[cur] + X[prev] - X[cur]
#        exp_once[cur] = exp
        X[cur] += exp

for x in X:
    print float(x)

Submission status: Accepted

Solution code:
import numpy as np


def test(n, xxx, m, k, aaa):
    # print(xxx)
    print(np.diff(xxx))
    for _ in range(k):
        for a in aaa:
            x, y, z = xxx[a - 2:a + 1]
            b = x - (y - x)
            c = z + (z - y)
            xxx[a - 1] = (b + c) // 2
        # print(xxx)
        print(np.diff(xxx))


n = int(input())
xxx = list(map(int, input().split()))
m, k = map(int, input().split())
aaa = list(map(int, input().split()))

doubling = np.arange(n - 1, dtype=np.int64)
for a in aaa:
    doubling[a - 2], doubling[a - 1] = doubling[a - 1], doubling[a - 2]

perm = np.arange(n - 1, dtype=np.int64)
while k:
    if k & 1:
        perm = perm[doubling]
    doubling = doubling[doubling]
    k >>= 1

diff = np.diff(xxx)[perm]
diff = np.insert(diff, 0, xxx[0])
print('\n'.join(map(str, diff.cumsum())))

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main(N, M, K, X, A):
    def compute_perm(A):
        P = np.arange(N - 1)
        for i in A:
            P[i - 2], P[i - 1] = P[i - 1], P[i - 2]
        return P

    def power(P, K):
        Q = P.copy()
        x = np.arange(len(P), dtype=np.int32)
        while K:
            if K & 1:
                x = x[Q]
            Q = Q[Q]
            K >>= 1
        return x

    P = compute_perm(A)
    P = power(P, K)
    D = X[1:] - X[:-1]
    D = D[P]
    ret = np.zeros(N, np.int64)
    ret[0] = X[0]
    ret[1:] = np.cumsum(D) + X[0]
    return ret

signature = '(i8,i8,i8,i8[:],i4[:])'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', signature)(main)
    cc.compile()

from my_module import main

N = int(readline())
X = np.array(readline().split(), np.int64)
M, K = map(int, readline().split())
A = np.array(readline().split(), np.int32)

x = main(N, M, K, X, A)
print('\n'.join(map(str, x.tolist())))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

"""
・対象のうさぎの期待値だけ分かれば、次時点での期待値が分かる
・期待値の差分Yを持つ。操作は、Y[i-1]とY[i]の交換
"""

N = int(readline())
X = np.zeros(N+1,np.int64)
X[1:] = readline().split()
M,K = map(int,readline().split())
A = list(map(int,read().split()))

Y = np.diff(X)

# newY[i] = Y[P[i]]
P = list(range(N))
for a in A:
    P[a],P[a-1] = P[a-1],P[a]
P = np.array(P)

def mult_perm(P,Q):
    return P[Q]

def power_perm(P,N):
    if N == 0:
        return np.arange(len(P))
    Q = power_perm(P,N//2)
    Q = mult_perm(Q,Q)
    return mult_perm(P,Q) if N & 1 else Q

Q = power_perm(P,K)

newY = Y[Q]
newX = np.cumsum(newY)

print('\n'.join(newX.astype(str)))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

def merge(A, B):
    N = len(A)
    res = [B[A[i]] for i in range(N)]
    return res

N = int(readline())

X = list(map(int, readline().split()))
M, K = map(int, readline().split())
A = list(map(lambda x:int(x)-1, readline().split()))
Y = [x2 - x1 for x1, x2 in zip(X, X[1:])]

 
P = list(range(N))
for a in A:
    P[a], P[a+1] = P[a+1], P[a]
stack = [P]
for _ in range(65):
    stack.append(merge(stack[-1], stack[-1]))

E = list(range(N))
for i in range(K.bit_length()):
    if (1<<i) & K:
        E = merge(E, stack[i])

Ans = [0]*N
Ans[0] = X[0]
for i in range(1, N):
    Ans[i] = Ans[i-1] + Y[E[i]-1]
print('\n'.join(map(str, Ans)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

"""
両端の位置が不変。x,y,z -> x,x+z-y,zを繰り返すが、階差数列で見るとswapに相当する。
"""

import numpy as np

N = int(input())
X = [int(x) for x in input().split()]
M,K = map(int,input().split())
A = [int(x) for x in input().split()]

P = list(range(N))
for a in A:
    P[a-1],P[a] = P[a],P[a-1]

P = np.array(P,dtype=np.int32)

def power(P,n):
    if n == 1:
        return P
    Q = power(P,n//2)
    Q = Q[Q]
    return P[Q] if n&1 else Q

Q = power(P,K)

diff = np.diff([0] + X)
answer = diff[Q].cumsum()
print('\n'.join(answer.astype(str)))

Submission status: Accepted

Solution code:
from numpy import*
n,*a=map(int,open(0).read().split())
*s,=t=arange(n-1)
for i in a[-a[n]:]:t[[i-2,i-1]]=t[[i-1,i-2]]
k=a[n+1]
while k:s=[s,t[s]][k%2];t=t[t];k//=2
print(*cumsum(a[:1]+list(diff(a[:n])[s])))

Submission status: Accepted

Solution code:
from numpy import*
n,*a=map(int,open(0).read().split())
t=arange(n-1)
*s,=t
for i in a[-a[n]:]:t[i-2],t[i-1]=t[i-1],t[i-2]
k=a[n+1]
while k:
    if k%2:s=t[s]
    t=t[t]
    k//=2
print(*cumsum(a[:1]+list(diff(a[:n])[s])))

Submission status: Accepted

Solution code:
n = int(input())
x = list(map(int, input().split()))
g = [x[i+1]-x[i] for i in range(n-1)]
m, k = map(int, input().split())
A = list(map(int, input().split()))
t = list(range(n-1))
for a in A:
	t[a-2], t[a-1] = t[a-1], t[a-2]
s = list(range(n-1))
while k > 0:
	if k&1:
		s = [s[t[i]] for i in range(n-1)]
	t = [t[t[i]] for i in range(n-1)]
	k >>= 1
new_g = [g[s[i]] for i in range(n-1)]
ans = [x[0]]
for i in range(n-1):
	ans.append(ans[-1] + new_g[i])
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
N=int(input())
X=[int(i) for i in input().split()]
dX=[]
for i in range(N-1):
  dX.append(X[i+1]-X[i])
M,K=map(int,input().split())
A=[int(i)-2 for i in input().split()]
Swap=[list(range(N-1)) for i in range(61)]
for a in A:
  Swap[0][a],Swap[0][a+1]=Swap[0][a+1],Swap[0][a]
for k in range(60):
  for i in range(N-1):
    Swap[k+1][i]=Swap[k][Swap[k][i]]
C=list(range(N-1))
for k in range(61)[::-1]:
  if K&(1<<k):
    for i in range(N-1):
      C[i]=Swap[k][C[i]]
new_dX=[0]*(N-1)
for i in range(N-1):
  new_dX[i]=dX[C[i]]
S=X[0]
print(X[0])
for i in range(N-1):
  S+=new_dX[i]
  print(S)

Submission status: Accepted

Solution code:
n = int(input())
x = list(map(int,input().split()))
m,k = map(int,input().split())
a = list(map(int,input().split()))
b = []
x2 = []
c = []
for i in range(1,n):
  b.append(i-1)
  x2.append(x[i]-x[i-1])
for i in range(m):
  to = a[i]-1
  b[to],b[to-1] = b[to-1],b[to]
c = [-1] * (n-1)
for i in range(n-1):
  c[b[i]] = i
for i in range(60):
  x3 = [0]*(n-1)
  if k&(1<<i):
    for i in range(n-1):
      x3[c[i]] = x2[i]
    x2 = x3
  c2 = [-1] * (n-1)
  for i in range(n-1):
    c2[i] = c[c[i]] 
  c = c2
s = x[0]
print(s)
for i in x2:
  s += i
  print(s)

Submission status: Accepted

Solution code:
def process(x, a, k):
    n = len(x)
    f = range(0, n)
    for i in a:
        f[i], f[i+1] = f[i+1], f[i]
    #print 'f=%s' % str(f)
    b = 1
    while b<=k:
        if (k&b)!=0:
            t = [0 for i in xrange(n)]
            for i in xrange(n):
                t[i] = x[f[i]]
            x = [i for i in t]
            #print 'x=%s' % str(x)
        t = [0 for i in f]
        for i in xrange(n):
            t[i] = f[f[i]]
        f = [i for i in t]
        #print 'f=%s' % str(f)
        b <<= 1
    return x

def main():
    n = int(raw_input().strip())
    x = [int(i) for i in raw_input().strip().split()]
    for i in xrange(len(x)-1, 0, -1):
        x[i] = x[i]-x[i-1]
    m, k = [int(i) for i in raw_input().strip().split()]
    a = [int(i) for i in raw_input().strip().split()]
    for i in xrange(len(a)):
        a[i] -= 2
    r = process(x[1:], a, k)
    print x[0]
    for i in xrange(1, len(x)):
        x[i] = x[i-1]+r[i-1]
        print x[i]

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import log

n = int(raw_input())
x = map(int, raw_input().split())
m, k = map(int, raw_input().split())
a = map(lambda x:int(x) - 2, raw_input().split())

logk = log(k, 2)
dy = [x[i + 1] - x[i] for i in xrange(n - 1)]
swap = [range(n - 1) for _ in xrange(int(logk + 1))]

for i in xrange(m):
    swap[0][a[i]], swap[0][a[i] + 1] = swap[0][a[i] + 1], swap[0][a[i]]

j = 1
while j <= logk:
    for i in xrange(n - 1):
        swap[j][i] = swap[j - 1][swap[j - 1][i]]
    j += 1

last = range(n - 1)
j = 0
while k >> j > 0:
    if (k >> j) & 1 == 1:
        for i in xrange(n - 1):
            last[i] = swap[j][last[i]]
    j += 1

ans = x[0]
print(ans)
for i in xrange(n - 1):
    ans += dy[last[i]]
    print(ans)

Submission status: Accepted

Solution code:
ii=lambda:map(int,raw_input().split())
n=int(raw_input())
x=ii()
m,k=ii()
a=ii()
y=[x[i+1]-x[i] for i in range(n-1)]
a=[a[i]-2 for i in range(m)]
p=[i for i in range(n-1)]
for i in a:
    p[i],p[i+1]=p[i+1],p[i]
bit=list(reversed(map(int,list(bin(k)[2:]))))
q=[[] for i in range(len(bit))]
ans=[i for i in range(n)]
for i in range(len(bit)):
    if i==0: q[0]=[p[j] for j in range(n-1)]
    else: q[i]=[q[i-1][q[i-1][j]] for j in range(n-1)]
    if bit[i]:ans=[q[i][ans[j]] for j in range(n-1)]
w=x[0]
print w
for i in range(n-1):
    w+=y[ans[i]]
    print w

Submission status: Runtime Error

Solution code:
from numpy import*
n,*a=map(int,open(0).read().split())
x=a[:n]
d=diff(x)
t=arange(n-1)
*s,=t
for i in a[-a[n]:]:t[i-2],t[i-1]=t[i-1],t[i-2]
k=a[n+1]
while k:
    if k%2:s=t[s]
    t=t[t]
    k//=2
print(*cumsum([x[0],*d[s]]))

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
x = list(map(int,input().split()))
m,k = map(int,input().split())
a = list(map(int,input().split()))
b = []
x2 = []
c = []
for i in range(1,n):
  b.append(i-1)
  x2.append(x[i]-x[i-1])
for i in range(m):
  to = a[i]-1
  b[to],b[to-1] = b[to-1],b[to]
bai = np.zeros((n-1,n-1),dtype = "int8")
for i in range(n-1):
  xx = b[i]
  bai[xx,i] = 1
bai = np.mat(bai)
bai = bai**k
x2 = np.dot(x2,bai)
x2 = np.array(x2)
s = x[0]
print(s)
for i in x2[0]:
  s += i
  print(s)