結果

問題 No.2209 Flip and Reverse
ユーザー FromBooskaFromBooska
提出日時 2023-10-02 13:50:27
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,849 bytes
コンパイル時間 317 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 144,868 KB
最終ジャッジ日時 2024-07-26 13:44:21
合計ジャッジ時間 8,006 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
52,096 KB
testcase_01 AC 38 ms
52,224 KB
testcase_02 AC 37 ms
52,352 KB
testcase_03 AC 38 ms
52,724 KB
testcase_04 AC 38 ms
52,608 KB
testcase_05 AC 38 ms
52,352 KB
testcase_06 AC 39 ms
52,224 KB
testcase_07 AC 41 ms
52,352 KB
testcase_08 WA -
testcase_09 AC 38 ms
52,352 KB
testcase_10 AC 39 ms
52,224 KB
testcase_11 WA -
testcase_12 AC 38 ms
52,608 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 AC 200 ms
141,136 KB
testcase_33 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 真ん中から貪欲法で必須項を変えていく、最後まで行ってTと同じにならなければ-1
# 毎回flipしたら間に合わないのでflip01管理
# 最後以外でハスの関係にあるとき、たとえばT01に対してS10の場合は変更なしでいいのでは

N = int(input())
S_temp = input()
T_temp = input()

S = []
T = []
for i in range(N):
    S.append(int(S_temp[i]))
    T.append(int(T_temp[i]))

flip = 0
ans = 0
for i in range((N-1)//2, -1, -1):
    j = N-1-i
    #print('i', i, 'j', j)
    if i == (N-1)//2:
        if flip == 0:
            if (S[i], S[j])==(T[i], T[j]) or (S[i], S[j])==(T[j], T[i]):
                continue

            if S[i]!=T[j]:
                S[i] ^= 1
                flip ^= 1
                ans += 1
            if S[j]!=T[i]:
                S[j] ^= 1
                flip ^= 1  
                ans += 1
        elif flip == 1:
            if (S[j], S[i])==(T[i], T[j]) or (S[j], S[i])==(T[j], T[i]):
                continue
                
            if S[j]!=T[j]:
                S[j] ^= 1
                flip ^= 1
                ans += 1
            if S[i]!=T[i]:
                S[i] ^= 1
                flip ^= 1  
                ans += 1    

    elif (N-1)//2 > i > 0:
        if flip == 0:
            if (S[i], S[j])==(T[i], T[j]):
                continue
                   
            if S[i]!=T[j]:
                S[i] ^= 1
                flip ^= 1
                ans += 1
            if S[j]!=T[i]:
                S[j] ^= 1
                flip ^= 1  
                ans += 1
        elif flip == 1:
            if (S[j], S[i])==(T[i], T[j]):
                continue
                              
            if S[j]!=T[j]:
                S[j] ^= 1
                flip ^= 1
                ans += 1
            if S[i]!=T[i]:
                S[i] ^= 1
                flip ^= 1  
                ans += 1
    elif i == 0:
        # different            
        if flip == 0:
            if (S[i], S[j])==(T[i], T[j]):
                continue
                          
            if S[i]!=T[j]:
                S[i] ^= 1
                flip ^= 1
                ans += 1
            if S[j]!=T[i]:
                S[j] ^= 1
                flip ^= 1  
                ans += 1        
        elif flip == 1:
            if (S[j], S[i])==(T[i], T[j]):
                continue
                            
            if S[j]!=T[j]:
                S[j] ^= 1
                flip ^= 1
                ans += 1
            if S[i]!=T[i]:
                S[i] ^= 1
                flip ^= 1  
                ans += 1 
    #print('i', i, 'j', j, 'flip', flip, 'ans', ans, 'S', S, 'T', T)
                
if flip == 0:
    final_S = S
elif flip == 1:
    final_S = S[::-1]
    
if final_S == T:
    print(ans)
else:
    print(-1)
0