Submission #62295435

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
N=int(input())
A=input().strip()
#node=[num,parent,L,R,convert0,convert1]
class Node:
    def __init__(self,n) -> None:
        self.num=n
        self.convert0=0
        self.convert1=0
    
memo={}
def dfs(L,R,num):
    S=Node(num)
    memo[num]=S
    if R-L==1:
        if int(A[L])==0:
            S.convert1=1
        else:
            S.convert0=1
        
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

N=int(input())
A=input().strip()

#node=[num,parent,L,R,convert0,convert1]
class Node:
    def __init__(self,n) -> None:
        self.num=n
        self.convert0=0
        self.convert1=0

    
memo={}
def dfs(L,R,num):
    S=Node(num)
    memo[num]=S
    if R-L==1:
        if int(A[L])==0:
            S.convert1=1
        else:
            S.convert0=1
        
        return int(A[L])
    
    else:
        tmp=0
        tmp+=dfs(L,L+(R-L)//3,num*3+1)
        tmp+=dfs(L+(R-L)//3,L+(R-L)*2//3,num*3+2)
        tmp+=dfs(L+(R-L)*2//3,R,num*3+3)
        c0=[memo[num*3+i+1].convert0 for i in range(3)]
        c1=[memo[num*3+i+1].convert1 for i in range(3)]
        c0.sort()
        c1.sort()
        match tmp:
            case 0:
                S.convert1=c1[1]+c1[0]
            case 1:
                S.convert1=c1[1]
            case 2:
                S.convert0=c0[1]
            case 3:
                S.convert0=c0[1]+c0[0]
        return tmp>>1
k=dfs(0,3**N,0)

if k==0:
    print(memo[0].convert1)
else:
    print(memo[0].convert0)

Submission Info

Judge Result