Problem:


Score : 500 points

Problem Statement

Snuke, who loves animals, built a zoo.

There are N animals in this zoo. They are conveniently numbered 1 through N, and arranged in a circle.
The animal numbered i (2≤i≤N-1) is adjacent to the animals numbered i-1 and i+1. Also, the animal numbered 1 is adjacent to the animals numbered 2 and N, and the animal numbered N is adjacent to the animals numbered N-1 and 1.

There are two kinds of animals in this zoo: honest sheep that only speak the truth, and lying wolves that only tell lies.

Snuke cannot tell the difference between these two species, and asked each animal the following question: "Are your neighbors of the same species?" The animal numbered i answered s_i. Here, if s_i is o, the animal said that the two neighboring animals are of the same species, and if s_i is x, the animal said that the two neighboring animals are of different species.

More formally, a sheep answered o if the two neighboring animals are both sheep or both wolves, and answered x otherwise.
Similarly, a wolf answered x if the two neighboring animals are both sheep or both wolves, and answered o otherwise.

Snuke is wondering whether there is a valid assignment of species to the animals that is consistent with these responses. If there is such an assignment, show one such assignment. Otherwise, print -1.

Constraints

3 ≤ N ≤ 10^{5}

s is a string of length N consisting of o and x.

Input

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

N
s

Output

If there does not exist an valid assignment that is consistent with s, print -1.
Otherwise, print an string t in the following format. The output is considered correct if the assignment described by t is consistent with s.

t is a string of length N consisting of S and W.

If t_i is S, it indicates that the animal numbered i is a sheep. If t_i is W, it indicates that the animal numbered i is a wolf.

Sample Input 1

6
ooxoox

Sample Output 1

SSSWWS

For example, if the animals numbered 1, 2, 3, 4, 5 and 6 are respectively a sheep, sheep, sheep, wolf, wolf, and sheep, it is consistent with their responses. Besides, there is another valid assignment of species: a wolf, sheep, wolf, sheep, wolf and wolf.

Let us remind you: if the neiboring animals are of the same species, a sheep answers o and a wolf answers x. If the neiboring animals are of different species, a sheep answers x and a wolf answers o.

Sample Input 2

3
oox

Sample Output 2

-1

Print -1 if there is no valid assignment of species.

Sample Input 3

10
oxooxoxoox

Sample Output 3

SSWWSSSWWS



Sample input:
6
ooxoox


Sample output:
SSSWWS

Submission status: Accepted

Solution code:
N = int(input())
s = input()
first = [['S','S'],['S','W'],['W','S'],['W','W']]
flag = 0
mojiretu = ''

def hypothesis(N,s,ans1,ans2):
    ans = [ans1,ans2]
    for i in range(1,N-1):
        if ans[i] == 'S':
            if s[i] == 'o':
                if ans[i-1] == 'S':
                    ans.append('S')
                else:
                    ans.append('W')
            elif s[i] == 'x':
                if ans[i-1] == 'S':
                    ans.append('W')
                else:
                    ans.append('S')
        if ans[i] == 'W':
            if s[i] == 'o':
                if ans[i-1] == 'S':
                    ans.append('W')
                else:
                    ans.append('S')
            elif s[i] == 'x':
                if ans[i-1] == 'S':
                    ans.append('S')
                else:
                    ans.append('W')
    return ans

def conf(ans_sub):
    flag2 = 0
    if ans_sub[0] == 'S' and s[0] == 'o':
        if ans_sub[1] == ans_sub[N-1]:
            if ans_sub[N-1] == 'S' and s[N-1] == 'o':
                if ans_sub[0] == ans_sub[N-2]:
                    flag2 = 1
            elif ans_sub[N-1] == 'S' and s[N-1] == 'x':
                if ans_sub[0] != ans_sub[N-2]:
                    flag2 = 1
            elif ans_sub[N-1] == 'W' and s[N-1] == 'o':
                if ans_sub[0] != ans_sub[N-2]:
                    flag2 = 1
            elif ans_sub[N-1] == 'W' and s[N-1] == 'x':
                if ans_sub[0] == ans_sub[N-2]:
                    flag2 = 1

    elif ans_sub[0] == 'S' and s[0] == 'x':
        if ans_sub[1] != ans_sub[N-1]:
            if ans_sub[N-1] == 'S' and s[N-1] == 'o':
                if ans_sub[0] == ans_sub[N-2]:
                    flag2 = 1
            elif ans_sub[N-1] == 'S' and s[N-1] == 'x':
                if ans_sub[0] != ans_sub[N-2]:
                    flag2 = 1
            elif ans_sub[N-1] == 'W' and s[N-1] == 'o':
                if ans_sub[0] != ans_sub[N-2]:
                    flag2 = 1
            elif ans_sub[N-1] == 'W' and s[N-1] == 'x':
                if ans_sub[0] == ans_sub[N-2]:
                    flag2 = 1

    elif ans_sub[0] == 'W' and s[0] == 'o':
        if ans_sub[1] != ans_sub[N-1]:
            if ans_sub[N-1] == 'S' and s[N-1] == 'o':
                if ans_sub[0] == ans_sub[N-2]:
                    flag2 = 1
            elif ans_sub[N-1] == 'S' and s[N-1] == 'x':
                if ans_sub[0] != ans_sub[N-2]:
                    flag2 = 1
            elif ans_sub[N-1] == 'W' and s[N-1] == 'o':
                if ans_sub[0] != ans_sub[N-2]:
                    flag2 = 1
            elif ans_sub[N-1] == 'W' and s[N-1] == 'x':
                if ans_sub[0] == ans_sub[N-2]:
                    flag2 = 1

    elif ans_sub[0] == 'W' and s[0] == 'x':
        if ans_sub[1] == ans_sub[N-1]:
            if ans_sub[N-1] == 'S' and s[N-1] == 'o':
                if ans_sub[0] == ans_sub[N-2]:
                    flag2 = 1
            elif ans_sub[N-1] == 'S' and s[N-1] == 'x':
                if ans_sub[0] != ans_sub[N-2]:
                    flag2 = 1
            elif ans_sub[N-1] == 'W' and s[N-1] == 'o':
                if ans_sub[0] != ans_sub[N-2]:
                    flag2 = 1
            elif ans_sub[N-1] == 'W' and s[N-1] == 'x':
                if ans_sub[0] == ans_sub[N-2]:
                    flag2 = 1

    if flag2 == 1:
        return 1
    else:
        return 0

for a in first:
    ans_sub = hypothesis(N,s,a[0],a[1])
    flag = conf(ans_sub)
    if flag == 1:
        for x in ans_sub:
            mojiretu += x
        print(mojiretu)
        break
    if flag == 0 and a == first[3]:
        print(-1)

Submission status: Accepted

Solution code:
n = int(input())
s = input()

def search(t0, t1):
    t = [t0, t1]
    for i in range(1, n+1):
        if t[i] == 'S':
            if s[i % n] == 'o':
                t.append(t[i-1])
            else:
                if t[i-1] == 'S':
                    t.append('W')
                else:
                    t.append('S')
        else:
            if s[i % n] == 'o':
                if t[i-1] == 'S':
                    t.append('W')
                else:
                    t.append('S')
            else:
                t.append(t[i-1])

    if t[0] == t[-2] and t[1] == t[-1]:
        return t[:-2]
    else:
        return None

flg = True
for i, j in [('W', 'W'), ('S', 'S'), ('S', 'W'), ('W', 'S')]:
    if not search(i, j) is None:
        ans = search(i, j)
        print(*ans, sep='')
        flg = False
        break

if flg:
    print(-1)

Submission status: Accepted

Solution code:
import sys
N = int(input())
s = input()
List = [['S','S'], ['S','W'], ['W','S'], ['W','W']]
for i in range(4):
    ans = List[i]
    for i in range(1,N):
        if i != N-1:
            if (ans[i-1] == ans[i] and s[i] == 'o') or (ans[i-1] != ans[i] and s[i] == 'x'):
                ans.append('S')
            else:
                ans.append('W')
        else:
            if ((((ans[N-1] == 'S' and s[N-1] == 'o') or (ans[N-1] == 'W' and s[N-1] == 'x')) and (ans[N-2] == ans[0])) or (((ans[N-1] == 'S' and s[N-1] == 'x') or (ans[N-1] == 'W' and s[N-1] == 'o')) and (ans[N-2] != ans[0]))) and ((((ans[0] == 'S' and s[0] == 'o') or (ans[0] == 'W' and s[0] == 'x')) and (ans[N-1] == ans[1])) or (((ans[0] == 'S' and s[0] == 'x') or (ans[0] == 'W' and s[0] == 'o')) and (ans[N-1] != ans[1]))):
                print(''.join(ans))
                sys.exit()
print(-1)

Submission status: Accepted

Solution code:
N=int(input())
s=input()
ans=[""]*4
#まず先頭が羊で、右が羊の時を考える
flag=0
animals=[""]*N
animals[0]="S"
if s[0] == "o":
    animals[N-1]="S"
    animals[1]="S"
else:
    animals[N-1]="W"
    animals[1]="S"
#print(animals)
for i in range(1,N-2):
    if animals[i]=="S":
        if s[i]=="o":
            animals[i+1]=animals[i-1]
        else:
            if animals[i-1]=="S":
                animals[i + 1] ="W"
            else:
                animals[i + 1] = "S"
    else:
        if s[i]=="x":
            animals[i + 1] = animals[i - 1]
        else:
            if animals[i-1]=="S":
                animals[i + 1] ="W"
            else:
                animals[i + 1] = "S"
    #print(animals)
if (animals[N-2]=="W"):
    if (animals[N-3]!=animals[N-1])and(s[N-2]=="o"):
        flag=flag+1
    elif (animals[N-3]==animals[N-1])and(s[N-2]=="x"):
        flag=flag+1
else:
    if (animals[N-3]!=animals[N-1])and(s[N-2]=="x"):
        flag=flag+1
    elif (animals[N-3]==animals[N-1])and(s[N-2]=="o"):
        flag=flag+1
if (animals[N-1]=="W"):
    if (animals[N-2]!=animals[0])and(s[N-1]=="o"):
        flag=flag+1
    elif (animals[N-2]==animals[0])and(s[N-1]=="x"):
        flag=flag+1
else:
    if (animals[N-2]!=animals[0])and(s[N-1]=="x"):
        flag=flag+1
    elif (animals[N-2]==animals[0])and(s[N-1]=="o"):
        flag=flag+1
if flag==2:
    ans[0]="".join(animals)
#print(ans)
#続いて先頭が羊で、右が狼の時を考える
flag=0
animals=[""]*N
animals[0]="S"
if s[0] == "o":
    animals[N-1]="W"
    animals[1]="W"
else:
    animals[N-1]="S"
    animals[1]="W"
#print(animals)
for i in range(1,N-2):
    if animals[i]=="S":
        if s[i]=="o":
            animals[i+1]=animals[i-1]
        else:
            if animals[i-1]=="S":
                animals[i + 1] ="W"
            else:
                animals[i + 1] = "S"
    else:
        if s[i]=="x":
            animals[i + 1] = animals[i - 1]
        else:
            if animals[i-1]=="S":
                animals[i + 1] ="W"
            else:
                animals[i + 1] = "S"
    #print(animals)
if (animals[N-2]=="W"):
    if (animals[N-3]!=animals[N-1])and(s[N-2]=="o"):
        flag=flag+1
    elif (animals[N-3]==animals[N-1])and(s[N-2]=="x"):
        flag=flag+1
else:
    if (animals[N-3]!=animals[N-1])and(s[N-2]=="x"):
        flag=flag+1
    elif (animals[N-3]==animals[N-1])and(s[N-2]=="o"):
        flag=flag+1
if (animals[N-1]=="W"):
    if (animals[N-2]!=animals[0])and(s[N-1]=="o"):
        flag=flag+1
    elif (animals[N-2]==animals[0])and(s[N-1]=="x"):
        flag=flag+1
else:
    if (animals[N-2]!=animals[0])and(s[N-1]=="x"):
        flag=flag+1
    elif (animals[N-2]==animals[0])and(s[N-1]=="o"):
        flag=flag+1
if flag==2:
    ans[1]="".join(animals)
#print(ans)
#続いて先頭が狼で、右が狼の時を考える
flag=0
animals=[""]*N
animals[0]="W"
if s[0] == "o":
    animals[N-1]="S"
    animals[1]="W"
else:
    animals[N-1]="W"
    animals[1]="W"
#print(animals)
for i in range(1,N-2):
    if animals[i]=="S":
        if s[i]=="o":
            animals[i+1]=animals[i-1]
        else:
            if animals[i-1]=="S":
                animals[i + 1] ="W"
            else:
                animals[i + 1] = "S"
    else:
        if s[i]=="x":
            animals[i + 1] = animals[i - 1]
        else:
            if animals[i-1]=="S":
                animals[i + 1] ="W"
            else:
                animals[i + 1] = "S"
    #print(animals)
if (animals[N-2]=="W"):
    if (animals[N-3]!=animals[N-1])and(s[N-2]=="o"):
        flag=flag+1
    elif (animals[N-3]==animals[N-1])and(s[N-2]=="x"):
        flag=flag+1
else:
    if (animals[N-3]!=animals[N-1])and(s[N-2]=="x"):
        flag=flag+1
    elif (animals[N-3]==animals[N-1])and(s[N-2]=="o"):
        flag=flag+1
if (animals[N-1]=="W"):
    if (animals[N-2]!=animals[0])and(s[N-1]=="o"):
        flag=flag+1
    elif (animals[N-2]==animals[0])and(s[N-1]=="x"):
        flag=flag+1
else:
    if (animals[N-2]!=animals[0])and(s[N-1]=="x"):
        flag=flag+1
    elif (animals[N-2]==animals[0])and(s[N-1]=="o"):
        flag=flag+1
if flag==2:
    ans[2]="".join(animals)
#print(ans)
#続いて先頭が狼で、右が羊の時を考える
flag=0
animals=[""]*N
animals[0]="W"
if s[0] == "o":
    animals[N-1]="W"
    animals[1]="S"
else:
    animals[N-1]="S"
    animals[1]="S"
#print(animals)
for i in range(1,N-2):
    if animals[i]=="S":
        if s[i]=="o":
            animals[i+1]=animals[i-1]
        else:
            if animals[i-1]=="S":
                animals[i + 1] ="W"
            else:
                animals[i + 1] = "S"
    else:
        if s[i]=="x":
            animals[i + 1] = animals[i - 1]
        else:
            if animals[i-1]=="S":
                animals[i + 1] ="W"
            else:
                animals[i + 1] = "S"
    #print(animals)
if (animals[N-2]=="W"):
    if (animals[N-3]!=animals[N-1])and(s[N-2]=="o"):
        flag=flag+1
    elif (animals[N-3]==animals[N-1])and(s[N-2]=="x"):
        flag=flag+1
else:
    if (animals[N-3]!=animals[N-1])and(s[N-2]=="x"):
        flag=flag+1
    elif (animals[N-3]==animals[N-1])and(s[N-2]=="o"):
        flag=flag+1
if (animals[N-1]=="W"):
    if (animals[N-2]!=animals[0])and(s[N-1]=="o"):
        flag=flag+1
    elif (animals[N-2]==animals[0])and(s[N-1]=="x"):
        flag=flag+1
else:
    if (animals[N-2]!=animals[0])and(s[N-1]=="x"):
        flag=flag+1
    elif (animals[N-2]==animals[0])and(s[N-1]=="o"):
        flag=flag+1
if flag==2:
    ans[3]="".join(animals)
#print(ans)
flag=0
for i in range(4):
    if ans[i]!="":
        print(ans[i])
        flag=1
        break
if flag==0:
    print("-1")

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())
S = input()

ans = ['S'] * N


def ok(ST):
    ret = ['S'] * N
    ret[-1] = ST[-1]
    ret[0] = ST[0]

    for i in range(0, N - 2):
        if ret[i] == 'S':
            if S[i] == 'o':
                ret[i + 1] = ret[i - 1]
            else:
                ret[i + 1] = 'W' if ret[i - 1] == 'S' else 'S'
        else:
            if S[i] == 'o':
                ret[i + 1] = 'W' if ret[i - 1] == 'S' else 'S'
            else:
                ret[i + 1] = ret[i - 1]

    for i in range(N):
        if S[i] == 'o' and ret[i] == 'S' and ret[i - 1] != ret[(i + 1) % N]:
            return False
        if S[i] == 'o' and ret[i] == 'W' and ret[i - 1] == ret[(i + 1) % N]:
            return False
        if S[i] == 'x' and ret[i] == 'S' and ret[i - 1] == ret[(i + 1) % N]:
            return False
        if S[i] == 'x' and ret[i] == 'W' and ret[i - 1] != ret[(i + 1) % N]:
            return False

    return "".join(ret)


def solve():
    for s in ["SS", "SW", "WS", "WW"]:
        r = ok(s)
        if r:
            print(r)
            return

    print(-1)


solve()

Submission status: Accepted

Solution code:
# solution
import io
from scipy.misc import comb

data = int(input())
inti = input()


def check(ans):
    for i in range(1, data - 1):
        if (ans[i] == 0) == (inti[i] == 'o'):
            ans += [ans[i - 1]]
        else:
            ans += [1 - ans[i - 1]]
    if ((inti[0] == 'o') == (ans[0] == 0)) != (ans[1] == ans[-1]):
        return
    if ((inti[-1] == 'o') == (ans[-1] == 0)) != (ans[-2] == ans[0]):
        return
    print(*['W' if _ else 'S' for _ in ans], sep='')
    exit()


check([0, 0])
check([0, 1])
check([1, 0])
check([1, 1])
print(-1)

Submission status: Accepted

Solution code:
n = int(input())
s = input()

ans = ['S']*(n)

ani0 = ['S','S','W','W']
ani1 = ['S','W','S','W']
anim1 = ['S','W','W','S']

for i in range(4):
    ans[0] = ani0[i]
    if s[0] == 'o':
        ans[-1] = anim1[i]
        ans[1] = ani1[i]
    else:
        ans[-1] = anim1[3-i]
        ans[1] = ani1[3-i]
        
    #print(ans)
        
    for j in range(1,n):
        if j >= n-2:
            if s[j] == 'o':
                if ans[j] == 'S':
                    if ans[j-1] == 'S':
                        if ans[(j+1)%n] == 'S':
                            if j == n-1:
                                print(*ans,sep='')
                                exit()
                        else:
                            break
                    else:
                        if ans[(j+1)%n] == 'W':
                            if j == n-1:
                                print(*ans,sep='')
                                exit()
                        else:
                            break
                else:
                    if ans[j-1] == 'S':
                        if ans[(j+1)%n] == 'W':
                            if j == n-1:
                                print(*ans,sep='')
                                exit()
                        else:
                            break
                    else:
                        if ans[(j+1)%n] == 'S':
                            if j == n-1:
                                print(*ans,sep='')
                                exit()
                        else:
                            break
            else:
                #print(ans)
                if ans[j] == 'S':
                    if ans[j-1] == 'S':
                        if ans[(j+1)%n] == 'W':
                            if j == n-1:
                                print(*ans,sep='')
                                exit()
                        else:
                            break
                    else:
                        if ans[(j+1)%n] == 'S':
                            if j == n-1:
                                print(*ans,sep='')
                                exit()
                        else:
                            break
                else:
                    if ans[j-1] == 'S':
                        if ans[(j+1)%n] == 'S':
                            if j == n-1:
                                print(*ans,sep='')
                                exit()
                        else:
                            break
                    else:
                        if ans[(j+1)%n] == 'W':
                            if j == n-1:
                                print(*ans,sep='')
                                exit()
                        else:
                            break
        if j == n-1:
            break
        
        if s[j] == 'o':
            if ans[j] == 'S':
                if ans[j-1] == 'S':
                    ans[j+1] = 'S'
                else:
                    ans[j+1] = 'W'
            else:
                if ans[j-1] == 'S':
                    ans[j+1] = 'W'
                else:
                    ans[j+1] = 'S'
        else:
            if ans[j] == 'S':
                if ans[j-1] == 'S':
                    ans[j+1] = 'W'
                else:
                    ans[j+1] = 'S'
            else:
                if ans[j-1] == 'S':
                    ans[j+1] = 'S'
                else:
                    ans[j+1] = 'W'
print(-1)

Submission status: Accepted

Solution code:
N=int(input())
s=input()
ans1="SS"
ans2="WS"
ans3="WW"
ans4="SW"
ans=[ans1,ans2,ans3,ans4]
c=0
for j in range(4):        
    for k in range(1,N-1):
        if s[k]=="o":
            if ans[j][k]=="S":
                ans[j]+=ans[j][-2]
            else:
                if ans[j][-2]=="W":
                    ans[j]+="S"
                else:
                    ans[j]+="W"
        if s[k]=="x":
            if ans[j][k]=="W":
                ans[j]+=ans[j][-2]
            else:
                if ans[j][-2]=="W":
                    ans[j]+="S"
                else:
                    ans[j]+="W"
    if s[0]=="o":
        if ans[j][0]=="S":
            if ans[j][-1]==ans[j][1]:
                if ans[j][-1]=="S":
                    if s[-1]=="o":
                        if ans[j][-2]==ans[j][0]:
                            print(ans[j])
                            c+=1
                            break
                    if s[-1]=="x":
                        if ans[j][-2]!=ans[j][0]:
                            print(ans[j])
                            c+=1
                            break
                if ans[j][-1]=="W":
                    if s[-1]=="o":
                        if ans[j][-2]!=ans[j][0]:
                            print(ans[j])
                            c+=1
                            break
                    if s[-1]=="x":
                        if ans[j][-2]==ans[j][0]:
                            print(ans[j])
                            c+=1
                            break
                    
        if ans[j][0]=="W":
            if ans[j][-1]!=ans[j][1]:
                if ans[j][-1]=="S":
                    if s[-1]=="o":
                        if ans[j][-2]==ans[j][0]:
                            print(ans[j])
                            c+=1
                            break
                    if s[-1]=="x":
                        if ans[j][-2]!=ans[j][0]:
                            print(ans[j])
                            c+=1
                            break
                if ans[j][-1]=="W":
                    if s[-1]=="o":
                        if ans[j][-2]!=ans[j][0]:
                            print(ans[j])
                            c+=1
                            break
                    if s[-1]=="x":
                        if ans[j][-2]==ans[j][0]:
                            print(ans[j])
                            c+=1
                            break
    if s[0]=="x":
        if ans[j][0]=="W":
            if ans[j][-1]==ans[j][1]:
                if ans[j][-1]=="S":
                    if s[-1]=="o":
                        if ans[j][-2]==ans[j][0]:
                            print(ans[j])
                            c+=1
                            break
                    if s[-1]=="x":
                        if ans[j][-2]!=ans[j][0]:
                            print(ans[j])
                            c+=1
                            break
                if ans[j][-1]=="W":
                    if s[-1]=="o":
                        if ans[j][-2]!=ans[j][0]:
                            print(ans[j])
                            c+=1
                            break
                    if s[-1]=="x":
                        if ans[j][-2]==ans[j][0]:
                            print(ans[j])
                            c+=1
                            break
        if ans[j][0]=="S":
            if ans[j][-1]!=ans[j][1]:
                if ans[j][-1]=="S":
                    if s[-1]=="o":
                        if ans[j][-2]==ans[j][0]:
                            print(ans[j])
                            c+=1
                            break
                    if s[-1]=="x":
                        if ans[j][-2]!=ans[j][0]:
                            print(ans[j])
                            c+=1
                            break
                if ans[j][-1]=="W":
                    if s[-1]=="o":
                        if ans[j][-2]!=ans[j][0]:
                            print(ans[j])
                            c+=1
                            break
                    if s[-1]=="x":
                        if ans[j][-2]==ans[j][0]:
                            print(ans[j])
                            c+=1
                            break
if c==0:
    print(-1)

Submission status: Accepted

Solution code:
N = int(input())
s = input()
inv = {'S':'W','W':'S'}

prefix = ['SS','SW','WS','WW']

def check_i(i): # check0,check-1だけすれば十分
    if s[i] == 'o' and ans[i] == 'S':
        if ans[i+1] != ans[i-1]:
            return False
    if s[i] == 'x' and ans[i] == 'S':
        if ans[i+1] == ans[i-1]:
            return False
    if s[i] == 'o' and ans[i] == 'W':
        if ans[i+1] == ans[i-1]:
            return False
    if s[i] == 'x' and ans[i] == 'W':
        if ans[i+1] != ans[i-1]:
            return False
    return True


for p in prefix:
    ans = p
    for i in range(1,N-1):
        if s[i] == 'o' and ans[i] == 'S':
            ans += ans[i-1]
        if s[i] == 'x' and ans[i] == 'S':
            ans += inv[ans[i-1]]
        if s[i] == 'o' and ans[i] == 'W':
            ans += inv[ans[i-1]]
        if s[i] == 'x' and ans[i] == 'W':
            ans += ans[i-1]
    if check_i(0) and check_i(-1):
        print(ans)
        exit()
print(-1)

Submission status: Accepted

Solution code:
def main():
    # import sys
    # readline = sys.stdin.buffer.readline
    # readlines = sys.stdin.buffer.readlines
    N = int(input())
    L = input()

    A = [None] * (N + 2)
    for a0, a1 in [(0, 0), (0, 1), (1, 0), (1, 1)]:
        A[0] = a0
        A[1] = a1
        for i in range(2, N + 1):
            a = A[i - 1]
            s = (L[i - 1] == 'x')
            A[i] = A[i - 2] ^ (a ^ s)
        A[N + 1] = A[N - 1] ^ (A[N] ^ (L[0] == 'x'))
        if A[0] == A[N] and A[1] == A[N + 1]:
            exists = True
            break
    else:
        exists = False

    if exists:
        ans = []
        for i in range(N):
            c = 'W' if A[i] else 'S'
            ans.append(c)
        print(''.join(ans))
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    # import sys
    # readline = sys.stdin.buffer.readline
    # readlines = sys.stdin.buffer.readlines
    N = int(input())
    L = input()

    A = [None] * (N + 1)
    for a0, a1 in [(0, 0), (0, 1), (1, 0), (1, 1)]:
        A[0] = a0
        A[1] = a1
        for i in range(2, N + 1):
            a = A[i - 1]
            s = 0 if L[i - 1] == 'o' else 1
            # if a == 0:
            #     if s == 0:
            #         A[i] = A[i - 2]
            #     elif s == 1:
            #         A[i] = A[i - 2] ^ 1
            # elif a == 1:
            #     if s == 0:
            #         A[i] = A[i - 2] ^ 1
            #     elif s == 1:
            #         A[i] = A[i - 2]
            A[i] = A[i - 2] ^ (a ^ s)
        am = A[1] ^ (A[0] ^ (L[0] == 'x'))
        if A[0] == A[N] and am == A[N - 1]:
            exists = True
            break
    else:
        exists = False

    if exists:
        ans = []
        for i in range(N):
            c = 'W' if A[i] else 'S'
            ans.append(c)
        print(''.join(ans))
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(lambda x: 0 if x == 'o' else 1, list(input())))
# o: 0, x: 1

def decode_animals(l):
    return "".join(list(map(lambda x: 'S' if x == 0 else 'W', animals)))

def check(first, second, pre_last, last, first_coment, last_coment):
    # 最初と最後の帳尻合わせ
    f1 = False
    if first == 0:
        if first_coment == 0:
            f1 = second == last
        else:
            f1 = second != last
    else:
        if first_coment == 0:
            f1 = second != last
        else:
            f1 = second == last
    f2 = False
    if last == 0:
        if last_coment == 0:
            f2 = first == pre_last
        else:
            f2 = first != pre_last
    else:
        if last_coment == 0:
            f2 = first != pre_last
        else:
            f2 = first == pre_last
    return f1 and f2

for i in range(4):
    animals = []
    for j in range(2):
        # S: 0, W: 1
        if i >> j & 1:
            animals.append(1)
        else:
            animals.append(0)
    for i in range(2, n):
        next_animal = 0
        if animals[i-1] == 0 and s[i-1] == 0 or animals[i-1] == 1 and s[i-1] == 1:
            next_animal = animals[i-2]
        elif animals[i-1] == 0 and s[i-1] == 1 or animals[i-1] == 1 and s[i-1] == 0:
            next_animal = [1, 0][animals[i-2]]
        animals.append(next_animal)
    if check(animals[0], animals[1], animals[-2], animals[-1], s[0], s[-1]):
        ans = decode_animals(animals)
        print(ans)
        exit()
print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
s = input()
t = [1 if i == 'o' else 0 for i in s]
def generate(res):
    for i in range(1,n):
        if res[-1]:
            if t[i]:
                if res[-2]:
                    res.append(1)
                else:
                    res.append(0)
            else:
                if res[-2]:
                    res.append(0)
                else:
                    res.append(1)
        else:
            if t[i]:
                if res[-2]:
                    res.append(0)
                else:
                    res.append(1)
            else:
                if res[-2]:
                    res.append(1)
                else:
                    res.append(0)
    return res

def ret(ans):
    res = ["S"]*n
    for i in range(n):
        if ans[i] == 0:
            res[i] = "W"
    return ''.join(res)

ans1 = [1]
ans2 = [1]
ans3 = [1]
ans4 = [1]
if t[0]:
    ans1.append(1)
    ans2.append(0)
    res1 = generate(ans1)
    res2 = generate(ans2)
    if res1[-1] == ans1[0] and ans1[1] == res1[-2]:
        print(ret(res1[:-1]))
        quit()
    elif res2[-1] == ans2[0] and ans2[1] == res2[-2]:
        print(ret(res2[:-1]))
        quit()
else:
    ans3.append(1)
    ans4.append(0)
    res3 = generate(ans3)
    res4 = generate(ans4)
    if res3[-1] == ans3[0] and ans3[1] != res3[-2]:
        print(ret(res3[:-1]))
        quit()
    elif res4[-1] == ans4[0] and ans4[1] != res4[-2]:
        print(ret(res4[:-1])) 
        quit()


ans5 = [0]
ans6 = [0]
ans7 = [0]
ans8 = [0]
if t[0]:
    ans5.append(1)
    ans6.append(0)
    res5 = generate(ans5)
    res6 = generate(ans6)
    if res5[-1] == ans5[0] and ans5[1] != res5[-2]:
        print(ret(res5[:-1]))
        quit()
    elif res6[-1] == ans6[0] and ans6[1] != res6[-2]:
        print(ret(res6[:-1]))
        quit()

else:
    ans7.append(1)
    ans8.append(0)
    res7 = generate(ans7)
    res8 = generate(ans8)
    if res7[-1] == ans7[0] and ans7[1] == res7[-2]:
        print(ret(res7[:-1]))
        quit()
    elif res8[-1] == ans8[0] and ans8[1] == res8[-2]:
        print(ret(res8[:-1]))
        quit()

print(-1)