Problem:


Score : 1500 points

Problem Statement

We have a grid with 3 rows and N columns.
The cell at the i-th row and j-th column is denoted (i, j).
Initially, each cell (i, j) contains the integer i+3j-3.

A grid with N=5 columns

Snuke can perform the following operation any number of times:

Choose a 3×3 subrectangle of the grid. The placement of integers within the subrectangle is now rotated by 180°.

An example sequence of operations (each chosen subrectangle is colored blue)

Snuke's objective is to manipulate the grid so that each cell (i, j) contains the integer a_{i,j}.
Determine whether it is achievable.

Constraints

5≤N≤10^5

1≤a_{i,j}≤3N

All a_{i,j} are distinct.

Input

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

N
a_{1,1} a_{1,2} ... a_{1,N}
a_{2,1} a_{2,2} ... a_{2,N}
a_{3,1} a_{3,2} ... a_{3,N}

Output

If Snuke's objective is achievable, print Yes. Otherwise, print No.

Sample Input 1

5
9 6 15 12 1
8 5 14 11 2
7 4 13 10 3

Sample Output 1

Yes

This case corresponds to the figure in the problem statement.

Sample Input 2

5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15

Sample Output 2

No

Sample Input 3

5
1 4 7 10 13
2 5 8 11 14
3 6 9 12 15

Sample Output 3

Yes

The objective is already achieved with the initial placement of the integers.

Sample Input 4

6
15 10 3 4 9 16
14 11 2 5 8 17
13 12 1 6 7 18

Sample Output 4

Yes

Sample Input 5

7
21 12 1 16 13 6 7
20 11 2 17 14 5 8
19 10 3 18 15 4 9

Sample Output 5

No



Sample input:
5
9 6 15 12 1
8 5 14 11 2
7 4 13 10 3


Sample output:
Yes

Submission status: Wrong Answer

Solution code:
n=int(input())
input()
t=list(range(2,2+(n-1)*3 +1,3))
k=sorted([int(i) for i in input().strip().split(" ")])
input()
if t==k:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

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

n = int(input())
a = [list(map(int, input().split())) for _ in range(3)]

for j in range(n):
    if not ((a[0][j] - 1 == a[1][j] and a[2][j] + 1 == a[1][j]) or (a[0][j] + 1 == a[1][j] and a[2][j] - 1 == a[1][j])):
        print("No")
        exit()

for j in range(n):
    if (j % 2) * (((a[0][j] - 1) // 3) % 2) == 1:
        print("No")
        exit()

# BIT
def add(a, w, bit):
    x = a
    while x <= n:
        bit[x] += w
        x += x & -x

def solve(a, bit):
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & -x
    return ret

bit_odd = [0] * (3*n+1)
inv_odd = 0
flip_even = 0
for j in range(n):
    if j % 2 == 1:
        if a[0][j] > a[1][j]:
            flip_even += 1
    else:
        inv_odd += j - solve(a[0][j], bit_odd)
        add(a[0][j], 1, bit_odd)
if flip_even % 2 != inv_odd % 2:
    print("No")
    exit()


bit_even = [0] * (3*n+1)
inv_even = 0
flip_odd = 0
for j in range(n):
    if j % 2 == 0:
        if a[0][j] > a[1][j]:
            flip_odd += 1
    else:
        inv_even += j - solve(a[0][j], bit_even)
        add(a[0][j], 1, bit_even)
if flip_odd % 2 != inv_even % 2:
    print("No")
    exit()

print("Yes")

Submission status: Accepted

Solution code:

"""

https://atcoder.jp/contests/agc006/tasks/agc006_e

まず、ちゃんと並んでない場合はだめ

3x+0
3x+1
3x+2
またはこれが上下反転されているもの以外が存在したら即NO
これを xと表すことにする。上下反転を-xと表すこととする
すると初期状態はxで表すと
1,2,3,4,5…,N　となる。

操作は、連続する3つを選び、両端を入れ替え、3つの項に-1を掛ける
となる。

そのため、偶奇が違う数があるとout
次に転倒数を考える。転倒数は交換するたびに1減る or 1増える
偶奇番目を分けて考える

交換すると、両端の偶奇の正負のパリティは変化しないが、反対側が変化する
よって、偶奇が逆の集合の転倒数を求める
→奇数ならば積は負・偶数なら積は正　が保たれる　そうでない場合はNO

それ以外はすべて作れるのか…？証明したい

 1 2 3 4
-3-2-1 4
-3-4 1 2

分からん…とりあえず出してみよう

"""

from sys import stdin
import sys

def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): #ind 1～aまでの和を求める
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret

N = int(stdin.readline())

a = []
for i in range(3):
    tmp = list(map(int,stdin.readline().split()))
    a.append(tmp)

lis = []
bi  = []

for j in range(N):
    a[0][j] -= 1
    a[1][j] -= 1
    a[2][j] -= 1
    if a[0][j]//3 == a[1][j]//3 == a[2][j]//3 and a[0][j]//3%2 == j%2:
        if a[0][j] > a[1][j] > a[2][j]:
            lis.append(a[0][j]//3)
            bi.append(-1)
        elif a[0][j] < a[1][j] < a[2][j]:
            lis.append(a[0][j]//3)
            bi.append(1)
        else:
            print ("No")
            sys.exit()
    else:
        print ("No")
        sys.exit()

evenall = 1
for i in range(0,N,2):
    evenall *= bi[i]
oddall = 1
for i in range(1,N,2):
    oddall *= bi[i]


a = lis
#print (a,bi)
#even
BIT = [0] * (N+2)
ans = 0
for i in range(0,N,2):
    ans += i//2 - bitsum(a[i]+1,BIT)
    bitadd(a[i]+1,1,BIT)

#print (ans , oddall)
if (ans % 2 == 0 and oddall == -1) or (ans % 2 == 1 and oddall == 1):
    print ("No")
    sys.exit()

#odd
BIT = [0] * (N+2)
ans = 0
for i in range(1,N,2):
    ans += i//2 - bitsum(a[i]+1,BIT)
    bitadd(a[i]+1,1,BIT)

#print (ans , evenall)
if (ans % 2 == 0 and evenall == -1) or (ans % 2 == 1 and evenall == 1):
    print ("No")
    sys.exit()

print ("Yes")

Submission status: Accepted

Solution code:
class BIT():
    def __init__(self,n):
        self.BIT=[0]*(n+1)
        self.num=n

    def query(self,idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        while idx <= self.num:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return

N=int(input())
a=[list(map(int,input().split())) for i in range(3)]
odd=[]
even=[]
for i in range(N):
    x,y,z=a[0][i],a[1][i],a[2][i]
    if x<z:
        if y!=x+1 or z!=y+1:
            print("No")
            exit()
        else:
            if i%2==0:
                if x%6==1:
                    even.append(x//6+1)
                else:
                    print("No")
                    exit()
            else:
                if x%6==4:
                    odd.append(x//6+1)
                else:
                    print("No")
                    exit()
    else:
        if y!=x-1 or z!=y-1:
            print("No")
            exit()
        else:
            if i%2==0:
                if z%6==1:
                    even.append(-(z//6)-1)
                else:
                    print("No")
                    exit()
            else:
                if z%6==4:
                    odd.append(-(z//6)-1)
                else:
                    print("No")
                    exit()

oddsign=0
ODD=[(abs(odd[i]),i) for i in range(len(odd))]
ODD.sort()
for i in range(len(odd)):
    val,id=ODD[i]
    check=(id-i)%2
    if check==1:
        oddsign+=(odd[id]>0)
    else:
        oddsign+=(odd[id]<0)

evensign=0
EVEN=[(abs(even[i]),i) for i in range(len(even))]
EVEN.sort()
for i in range(len(even)):
    val,id=EVEN[i]
    check=(id-i)%2
    if check==1:
        evensign+=(even[id]>0)
    else:
        evensign+=(even[id]<0)

oddbit=BIT(len(odd))
check=0
for i in range(len(odd)):
    v=abs(odd[i])
    check+=i-oddbit.query(v)
    oddbit.update(v,1)

if check%2!=evensign%2:
    print("No")
    exit()

evenbit=BIT(len(even))
check=0
for i in range(len(even)):
    v=abs(even[i])
    check+=i-evenbit.query(v)
    evenbit.update(v,1)

if check%2!=oddsign%2:
    print("No")
    exit()

print("Yes")

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N = I()
a = [LI() for i in range(3)]

A = []
B = []
c = 0
d = 0

for i in range(N):
    if i % 2 == 0:
        if a[0][i] % 6 == 1 and a[1][i] % 6 == 2 and a[2][i] % 6 == 3:
            A.append(a[1][i]//6)
        elif a[0][i] % 6 == 3 and a[1][i] % 6 == 2 and a[2][i] % 6 == 1:
            c += 1
            A.append(a[1][i]//6)
        else:
            print('No')
            exit()
    else:
        if a[0][i] % 6 == 4 and a[1][i] % 6 == 5 and a[2][i] % 6 == 0:
            B.append(a[1][i]//6)
        elif a[0][i] % 6 == 0 and a[1][i] % 6 == 5 and a[2][i] % 6 == 4:
            d += 1
            B.append(a[1][i]//6)
        else:
            print('No')
            exit()


class SegmentTree():
    def __init__(self,init_value,seg_func,unit_elt):
        n = len(init_value)
        self.seg_func = seg_func
        self.unit_elt = unit_elt
        self.num = 1 << (n-1).bit_length()  # n以上の最小2冪
        self.tree = [unit_elt]*(2*self.num)
        for i in range(n):
            self.tree[self.num + i] = init_value[i]
        for i in range(self.num-1,0,-1):
            self.tree[i] = self.seg_func(self.tree[2*i],self.tree[2*i+1])
    def update(self,i,x):  # i(0-index)番目の値をxに更新
         i += self.num
         self.tree[i] = x
         while i > 1:
             i >>= 1
             self.tree[i] = self.seg_func(self.tree[2*i],self.tree[2*i+1])
    def quary(self,p,q):  # [p,q)に関するseg_funcの結果を返す(p,qは0-index)
        p += self.num
        q += self.num
        res = self.unit_elt
        while p < q:
            if p & 1:
                res = self.seg_func(res,self.tree[p])
                p += 1
            if q & 1:
                res = self.seg_func(res,self.tree[q-1])
            p >>= 1
            q >>= 1
        return res

def seg_func(x,y):
    return x + y

seg1 = SegmentTree([0]*(len(A)),seg_func,unit_elt=0)
seg2 = SegmentTree([0]*(len(B)),seg_func,unit_elt=0)

a = 0  # Aの転倒数
for i in range(len(A)):
    a += i-seg1.quary(0,A[i])
    seg1.update(A[i],1)
b = 0  # Bの転倒数
for i in range(len(B)):
    b += i-seg2.quary(0,B[i])
    seg2.update(B[i],1)

if (a-d) % 2 == 0 and (b-c) % 2 == 0:
    print('Yes')
else:
    print('No')

Submission status: Accepted

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

from operator import itemgetter, mul
from functools import reduce

N = int(readline())
A = list(map(int,readline().split()))
B = list(map(int,readline().split()))
C = list(map(int,readline().split()))

sgn = [0] * N
for i,(a,b,c) in enumerate(zip(A,B,C)):
    if a == b-1 and c == b+1:
        sgn[i] = 1
    elif a == b+1 and c == b-1:
        sgn[i] = -1
    else:
        print('No')
        exit()

if any(x%6 != 2 for x in B[::2]) or any(x%6 != 5 for x in B[1::2]):
    print('No')
    exit()

class BinaryIndexedTree():
    def __init__(self, seq):
        self.size = len(seq)
        self.depth = self.size.bit_length()
        self.build(seq)
        
    def build(self,seq):
        data = seq
        size = self.size
        for i,x in enumerate(data):
            j = i+(i&(-i))
            if j < size:
                data[j] += data[i]
        self.data = data
        
    def __repr__(self):
        return self.data.__repr__()
        
    def get_sum(self,i):
        data = self.data
        s = 0
        while i:
            s += data[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        data = self.data
        size = self.size
        while i < size:
            data[i] += x
            i += i & -i
    
    def find_kth_element(self,k):
        data = self.data; size = self.size
        x,sx = 0,0
        dx = 1 << (self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= size:
                continue
            y = x + dx
            sy = sx + data[y]
            if sy < k:
                x,sx = y,sy
        return x + 1

def Inversion(seq):
    # seqは、1,2,...,Nの順列
    N = len(seq)
    bit = BinaryIndexedTree([0] * (N+1))
    inv = N*(N-1)//2
    for x in seq:
        inv -= bit.get_sum(x)
        bit.add(x,1)
    return inv

OD = sorted(enumerate(B[::2],1), key=itemgetter(1))
ind, val = zip(*OD)
od_inv = Inversion(ind)

EV = sorted(enumerate(B[1::2],1), key=itemgetter(1))
ind, val = zip(*EV)
ev_inv = Inversion(ind)

od_sgn = reduce(mul, sgn[::2])
ev_sgn = reduce(mul, sgn[1::2])

condition = (od_sgn == (-1)**ev_inv) and (ev_sgn == (-1)**od_inv)

answer = 'Yes' if condition else 'No'
print(answer)

Submission status: Accepted

Solution code:
n = int(input())

a = []
for i in range(3):
    aa = list(map(int,input().split()))
    a.append(aa)

for i in range(n):
    x,y,z = a[0][i],a[1][i],a[2][i]
    x,z = x-y,z-y
    if i % 2 == 0:
        if y % 6 != 2:
            print("No")
            exit()
    else:
         if y % 6 != 5:
            print("No")
            exit()       
    y = 0
    if (x,y,z) != (-1,0,1) and (x,y,z) != (1,0,-1):
        print("No")
        exit()
        


e,o = 0,0
for i in range(n):
    if i % 2 == 0:
        if a[0][i] > a[2][i]: e += 1
    else:
        if a[0][i] > a[2][i]: o += 1

e %= 2
o %= 2

el = []
ol = []
bite = [0]
bito = [0]

for i in range(n):
    if(i % 2 == 0):
        el.append(a[1][i] // 6 + 1)
        bite.append(0)
    else:
        ol.append(a[1][i] // 6 + 1)
        bito.append(0)

def sum(i,bit):
    s = 0
    while(i > 0):
        s += bit[i]
        i = i&(i-1)
    return s
 
def add(i,x,bit):
    while(i < len(bit)):
        bit[i] += x
        i += i & (-i)

signe = 0
signo = 0

for i in range(len(el)):
    signe += (i - sum(el[i],bite))
    add(el[i],1,bite)    

for i in range(len(ol)):
    signo += (i - sum(ol[i],bito))
    add(ol[i],1,bito) 



if (signe % 2 == o) and (signo % 2 == e) :print("Yes")
else :print("No")

Submission status: Accepted

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

n = int(input())
a = [list(map(int, input().split())) for _ in range(3)]

for j in range(n):
    if not ((a[0][j] - 1 == a[1][j] and a[2][j] + 1 == a[1][j]) or (a[0][j] + 1 == a[1][j] and a[2][j] - 1 == a[1][j])):
        print("No")
        exit()

for j in range(n):
    if (j % 2) ^ (((a[0][j] - 1) // 3) % 2) == 1:
        print("No")
        exit()

# BIT
def add(a, w, bit):
    x = a
    while x <= 3 * n:
        bit[x] += w
        x += x & -x

def solve(a, bit):
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & -x
    return ret

bit_odd = [0] * (3*n+1)
inv_odd = 0
flip_even = 0
for j in range(n):
    if j % 2 == 1:
        if a[0][j] > a[1][j]:
            flip_even += 1
    else:
        inv_odd += j//2 - solve(a[0][j], bit_odd)
        add(a[0][j], 1, bit_odd)
if flip_even % 2 != inv_odd % 2:
    print("No")
    exit()


bit_even = [0] * (3*n+1)
inv_even = 0
flip_odd = 0
for j in range(n):
    if j % 2 == 0:
        if a[0][j] > a[1][j]:
            flip_odd += 1
    else:
        inv_even += j//2 - solve(a[0][j], bit_even)
        add(a[0][j], 1, bit_even)
if flip_odd % 2 != inv_even % 2:
    print("No")
    exit()

print("Yes")

Submission status: Accepted

Solution code:
def merge_and_count_rec(A, W, l, r):
    if l+1 >= r:
        return 0
    m = (l+r)//2
    cnt  = merge_and_count_rec(A, W, l, m)
    cnt += merge_and_count_rec(A, W, m, r)
    i,j,k = l,m,l
    while i<m and j<r:
        if A[i]<=A[j]:
            W[k] = A[i]
            i+=1
        else:
            W[k] = A[j]
            j+=1
            cnt += m-i
        k+=1
    if i<m:
        W[k:r] = A[i:m]
    if j<r:
        W[k:r] = A[j:r]
    A[l:r] = W[l:r]
    return cnt

N = int(input())
A = tuple(list(map(int,input().split())) for _ in range(3))
O = []
ok = True
flip = [0,0]
for i in range(N):
    ok &= (A[1][i] % 3) == 2
    ok &= sorted((A[0][i], A[1][i], A[2][i]))==[A[1][i]-1, A[1][i], A[1][i]+1]
    dist = abs(A[1][i]//3 - i)
    ok &= (dist % 2) == 0
    order = [A[0][i], A[1][i], A[2][i]] == [A[1][i]-1, A[1][i], A[1][i]+1]
    if ((dist//2)%2 == 0) != order:
        flip[i%2] += 1

B = A[1][0::2]
hb = merge_and_count_rec(B, A[0], 0, len(B))
C = A[1][1::2]
hc = merge_and_count_rec(C, A[0], 0, len(C))

ok &= (hb % 2) == (flip[1]%2)
ok &= (hc % 2) == (flip[0]%2)
print("Yes" if ok else "No")