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()
ans = ""
def next_animal(pre,now,letter):
    if pre == "S" and now == "S" and letter == "o":
        return "S"
    if pre == "S" and now == "S" and letter == "x":
        return "W"
    if pre == "S" and now == "W" and letter == "o":
        return "W"
    if pre == "S" and now == "W" and letter == "x":
        return "S"
    if pre == "W" and now == "S" and letter == "o":
        return "W"
    if pre == "W" and now == "S" and letter == "x":
        return "S"
    if pre == "W" and now == "W" and letter == "o":
        return "S"
    if pre == "W" and now == "W" and letter == "x":
        return "W"

for case in range(4):
    if case == 0:
        ans = "SS"
    if case == 1:
        ans = "SW"
    if case == 2:
        ans = "WS"
    if case == 3:
        ans = "WW"
    for i in range(1,n-1):
        next = next_animal(ans[-1],ans[-2],s[i])
        ans += next
    if ans[-1] == next_animal(ans[1],ans[0],s[0]) and ans[0] == next_animal(ans[-2],ans[-1],s[-1]):
        print(ans)
        exit()

print(-1)

Submission status: Accepted

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

cand = ["S","W"]

ch = {"S":"W", "W":"S", "o":"x", "x":"o"}

def func(now_animal, pre_animal, mark):
    if now_animal == "W":
        mark = ch[mark]
    if mark == "o":
        return pre_animal
    else:
        return ch[pre_animal]

def judge(now_animal, pre_animal, next_animal, mark):
    if now_animal == "W":
        mark = ch[mark]
    if (mark == "o" and pre_animal == next_animal) or (mark == "x" and pre_animal != next_animal):
        return True
    else:
        return False

for a in cand:
    for b in cand:
        tmp = a + b
        # i番目を決める
        for i in range(2,N):
            tmp += func(tmp[i-1], tmp[i-2], s[i-1])
        if judge(tmp[-1], tmp[-2], tmp[0], s[-1]) and judge(tmp[0], tmp[-1], tmp[1], s[0]):
            print(tmp)
            exit()

print(-1)

Submission status: Accepted

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

possible = 0
finish_flag = 0
for animal0 in range(2):
    if finish_flag == 1:
        break
    for animal1 in range(2):
        if finish_flag == 1:
            break
        animal = [0] * N
        animal[0] = animal0
        animal[1] = animal1
        for i in range(1, N - 1):
            if animal[i] == 0:
                animal[i + 1] = animal[i - 1] if s[i] == 'o' else (animal[i - 1] + 1) % 2
            else:
                animal[i + 1] = (animal[i - 1] + 1) % 2 if s[i] == 'o' else animal[i - 1]
        if animal[N - 1] == 0:
            animal0_true = animal[N - 2] if s[N - 1] == 'o' else (animal[N - 2] + 1) % 2
        else:
            animal0_true = (animal[N - 2] + 1) % 2 if s[N - 1] == 'o' else animal[N - 2]
        if animal[0] == 0:
            animal1_true = animal[N - 1] if s[0] == 'o' else (animal[N - 1] + 1) % 2
        else:
            animal1_true = (animal[N - 1] + 1) % 2 if s[0] == 'o' else animal[N - 1]
        if animal0 == animal0_true and animal1 == animal1_true:
            possible = 1
            finish_flag = 1

if possible:
    ans = [0] * N
    for i in range(N):
        ans[i] = 'S' if animal[i] == 0 else 'W'
    print("".join(ans))
else:
    print(-1)

Submission status: Accepted

Solution code:
import itertools
import math
N = int(input())
S = input()
l = len(S)


#oxooxoxoox
#s → 1 w→-1
temp = []
for c in S:
    if c == "o":
        temp.append(1)
    else:
        temp.append(-1)

S = temp

flag = False
for i in [1,-1]: # 1匹目
    for j in [1,-1]: #2匹目
        nums = [i,j]
        temp = i * j
        for k in range(1,N-1):
            nums.append(temp * S[k])
            temp = nums[k] * nums[k  + 1]
        if temp * nums[0] == S[-1]  and nums[-1] * nums[0] * nums[1] == S[0]:
            flag = True
            break
    if flag:
        break

if flag:
    for num in nums:
        if num == -1:
            print("W",end="")
        else:
            print("S", end="")

else:
    print(-1)

Submission status: Accepted

Solution code:
n=int(input())
arr=input()
ans=['S']*n
cnt=0
for i in range(1,n-1):
  if arr[i]=='o':
    if ans[i]=='S':
      if ans[i-1]==ans[(i+1)%n]:
        continue
      else:
        ans[(i+1)%n]=ans[i-1]
    elif ans[i]=='W':
      if ans[i-1]!=ans[(i+1)%n]:
        continue
      else:
        if ans[(i+1)%n]=='S':
          ans[(i+1)%n]='W'
        else:
          ans[(i+1)%n]='S'
  elif arr[i]=='x':
    if ans[i]=='S':
      if ans[i-1]==ans[(i+1)%n]:
        if ans[(i+1)%n]=='S':
          ans[(i+1)%n]='W'
        else:
          ans[(i+1)%n]='S'
      else:
        continue
    elif ans[i]=='W':
      if ans[i-1]==ans[(i+1)%n]:
        continue
      else:
        if ans[(i+1)%n]=='S':
          ans[(i+1)%n]='W'
        else:
          ans[(i+1)%n]='S'
flag=False
for i in range(n):
  if arr[i]=='o':
    if ans[i]=='S':
      if ans[i-1]==ans[(i+1)%n]:
        continue
      else:
        break
    elif ans[i]=='W':
      if ans[i-1]!=ans[(i+1)%n]:
        continue
      else:
        break
  elif arr[i]=='x':
    if ans[i]=='S':
      if ans[i-1]==ans[(i+1)%n]:
        break
      else:
        continue
    elif ans[i]=='W':
      if ans[i-1]==ans[(i+1)%n]:
        continue
      else:
        break
else:
  flag=True
if flag==True and cnt==0:
  print(''.join(map(str,ans)))
  cnt+=1
ans=['W']*n
for i in range(1,n-1):
  if arr[i]=='o':
    if ans[i]=='S':
      if ans[i-1]==ans[(i+1)%n]:
        continue
      else:
        ans[(i+1)%n]=ans[i-1]
    elif ans[i]=='W':
      if ans[i-1]!=ans[(i+1)%n]:
        continue
      else:
        if ans[(i+1)%n]=='S':
          ans[(i+1)%n]='W'
        else:
          ans[(i+1)%n]='S'
  elif arr[i]=='x':
    if ans[i]=='S':
      if ans[i-1]==ans[(i+1)%n]:
        if ans[(i+1)%n]=='S':
          ans[(i+1)%n]='W'
        else:
          ans[(i+1)%n]='S'
      else:
        continue
    elif ans[i]=='W':
      if ans[i-1]==ans[(i+1)%n]:
        continue
      else:
        if ans[(i+1)%n]=='S':
          ans[(i+1)%n]='W'
        else:
          ans[(i+1)%n]='S'
flag=False
for i in range(n):
  if arr[i]=='o':
    if ans[i]=='S':
      if ans[i-1]==ans[(i+1)%n]:
        continue
      else:
        break
    elif ans[i]=='W':
      if ans[i-1]!=ans[(i+1)%n]:
        continue
      else:
        break
  elif arr[i]=='x':
    if ans[i]=='S':
      if ans[i-1]==ans[(i+1)%n]:
        break
      else:
        continue
    elif ans[i]=='W':
      if ans[i-1]==ans[(i+1)%n]:
        continue
      else:
        break
else:
  flag=True
if flag==True and cnt==0:
  print(''.join(map(str,ans)))
  cnt+=1
ans=['S']*n
ans[1]='W'
for i in range(1,n-1):
  if arr[i]=='o':
    if ans[i]=='S':
      if ans[i-1]==ans[(i+1)%n]:
        continue
      else:
        ans[(i+1)%n]=ans[i-1]
    elif ans[i]=='W':
      if ans[i-1]!=ans[(i+1)%n]:
        continue
      else:
        if ans[(i+1)%n]=='S':
          ans[(i+1)%n]='W'
        else:
          ans[(i+1)%n]='S'
  elif arr[i]=='x':
    if ans[i]=='S':
      if ans[i-1]==ans[(i+1)%n]:
        if ans[(i+1)%n]=='S':
          ans[(i+1)%n]='W'
        else:
          ans[(i+1)%n]='S'
      else:
        continue
    elif ans[i]=='W':
      if ans[i-1]==ans[(i+1)%n]:
        continue
      else:
        if ans[(i+1)%n]=='S':
          ans[(i+1)%n]='W'
        else:
          ans[(i+1)%n]='S'
flag=False
for i in range(n):
  if arr[i]=='o':
    if ans[i]=='S':
      if ans[i-1]==ans[(i+1)%n]:
        continue
      else:
        break
    elif ans[i]=='W':
      if ans[i-1]!=ans[(i+1)%n]:
        continue
      else:
        break
  elif arr[i]=='x':
    if ans[i]=='S':
      if ans[i-1]==ans[(i+1)%n]:
        break
      else:
        continue
    elif ans[i]=='W':
      if ans[i-1]==ans[(i+1)%n]:
        continue
      else:
        break
else:
  flag=True
if flag==True and cnt==0:
  print(''.join(map(str,ans)))
  cnt+=1
ans=['W']*n
ans[1]='S'
for i in range(1,n-1):
  if arr[i]=='o':
    if ans[i]=='S':
      if ans[i-1]==ans[(i+1)%n]:
        continue
      else:
        ans[(i+1)%n]=ans[i-1]
    elif ans[i]=='W':
      if ans[i-1]!=ans[(i+1)%n]:
        continue
      else:
        if ans[(i+1)%n]=='S':
          ans[(i+1)%n]='W'
        else:
          ans[(i+1)%n]='S'
  elif arr[i]=='x':
    if ans[i]=='S':
      if ans[i-1]==ans[(i+1)%n]:
        if ans[(i+1)%n]=='S':
          ans[(i+1)%n]='W'
        else:
          ans[(i+1)%n]='S'
      else:
        continue
    elif ans[i]=='W':
      if ans[i-1]==ans[(i+1)%n]:
        continue
      else:
        if ans[(i+1)%n]=='S':
          ans[(i+1)%n]='W'
        else:
          ans[(i+1)%n]='S'
flag=False
for i in range(n):
  if arr[i]=='o':
    if ans[i]=='S':
      if ans[i-1]==ans[(i+1)%n]:
        continue
      else:
        break
    elif ans[i]=='W':
      if ans[i-1]!=ans[(i+1)%n]:
        continue
      else:
        break
  elif arr[i]=='x':
    if ans[i]=='S':
      if ans[i-1]==ans[(i+1)%n]:
        break
      else:
        continue
    elif ans[i]=='W':
      if ans[i-1]==ans[(i+1)%n]:
        continue
      else:
        break
else:
  flag=True
if flag==True and cnt==0:
  print(''.join(map(str,ans)))
  cnt+=1
if cnt==0:
  print(-1)

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())

# Sの値を+-1にする
for i in range(N) :
    if S[i] == 'o' :
        S[i] = 1
    else :
        S[i] = -1

S.append(S[0])

def check() :
    for first in [1, -1] :
        for second in [1, -1] :
            animal = [1] * (N + 2)
            animal[0] = first
            animal[1] = second
            for i in range(1,N+1) :
                if animal[i] == 1 :  # 動物が羊の場合
                    animal[i+1] = animal[i-1] *  S[i]
                else :  # 動物が狼の場合
                    animal[i+1] = animal[i-1] * S[i] * (-1)
            if animal[-2] == first and animal[-1] == second :
                return animal
    return -1

ans = check()

if ans == -1 :
    print(-1)
else :
    for i in range(N) :
        if ans[i] == 1 :
            print('S', end='')
        else :
            print('W', end='')
    print('')

Submission status: Accepted

Solution code:
n=int(input())
s=input()
def f(x,y):
  ret=x+y
  for i in range(2,n):
    if s[i-1]=="o" and ret[-1]=="S":
      ret+=ret[-2]
    elif s[i-1]=="o" and ret[-1]=="W":
      if ret[-2]=="S":
        ret+="W"
      else:
        ret+="S"
    elif s[i-1]=="x" and ret[-1]=="S":
      if ret[-2]=="S":
        ret+="W"
      else:
        ret+="S"
    elif s[i-1]=="x" and ret[-1]=="W":
      ret+=ret[-2]
  return ret
def chk(A):
  B=[A[-2],A[-1],A[0],A[1]]
  ret=True
  if s[-1]=="o":
    if B[1]=="S":
      if B[0]!=B[2]:
        ret=False
    else:
      if B[0]==B[2]:
        ret=False
  else:
    if B[1]=="S":
      if B[0]==B[2]:
        ret=False
    else:
      if B[0]!=B[2]:
        ret=False
  if s[0]=="o":
    if B[2]=="S":
      if B[1]!=B[3]:
        ret=False
    else:
      if B[1]==B[3]:
        ret=False
  else:
    if B[2]=="S":
      if B[1]==B[3]:
        ret=False
    else:
      if B[1]!=B[3]:
        ret=False
  return ret
if chk(f("S","S")):
  print(f("S","S"))
elif chk(f("S","W")):
  print(f("S","W"))
elif chk(f("W","S")):
  print(f("W","S"))
elif chk(f("W","W")):
  print(f("W","W"))
else:
  print(-1)

Submission status: Accepted

Solution code:
N = int(input())
S = input()


Flag = False

for dp,dq in [[0,0],[0,1],[1,0],[1,1]]:
  D = [dq,dp]
  for v in S:
    #D.append( "S" if p==1 else "W" )
    if v == "o" and D[-1] == 1:
      D.append(D[-2])
    elif v == "o" and D[-1] == 0:
      D.append(1-D[-2])
    elif v == "x" and D[-1] == 1:
      D.append(1-D[-2])
    elif v == "x" and D[-1] == 0:
      D.append(D[-2])
  if ( D[0]==D[-2] and D[1]==D[-1] ):
    Flag = True
    break
if ( Flag ):
  print ( "".join( map(lambda x:"S" if x==1 else "W",D[1:-1]) ) )
else:
  print (-1)

Submission status: Accepted

Solution code:
def check(l):
    globals()
    for i in range(1,n):
        d = 1 if s[i]=='o' else -1
        l.append(l[i-1]*l[i]*d)
    d = 1 if s[0]=='o' else -1
    if l[-2]*l[0]*d==l[1] and l[-1]==l[0]:
        for i in l[:n]:
            c = 'S' if i == 1 else 'W'
            print(c, end='')
    return l[-2]*l[0]*d==l[1] and l[-1]==l[0]
n = int(input())
s = input()
tests = [[1,1],[1,-1],[-1,1],[-1,-1]]
for t in tests:
    if check(t):
        exit()
print(-1)

Submission status: Accepted

Solution code:
n=int(input())
s=input()*2
for a in[['S','S'],['S','W'],['W','S'],['W','W']]:
    for i in range(1,n+1):
        f=a[i]+s[i]
        if f=='So'or'Wx'==f:
            a+=[a[i-1]]
        else:
            a+=[a[i-1].translate({83:87,87:83})]
    if a[:2]==a[n:]:
        print(''.join(a[:n]))
        break
else:
    print(-1)

Submission status: Accepted

Solution code:
#D問題
N = int(input())
Slist = list(str(input()))
flag = 0

anslist = []
maeflag = ""
froflag = ""
for i in range(N):
    if i == 0:
        anslist.append("S")
        if Slist[0] == "o":
            maeflag = "S"
        else:
            maeflag = "W"
    elif i == 1:
        anslist.append("S")
        if Slist[i] == "o":
            anslist.append("S")
        else:
            anslist.append("W")
    elif i < N-1:
        if Slist[i] == "o":
            if anslist[i] == "S":
                anslist.append(anslist[i-1])
            else:
                if anslist[i-1] == "S":
                    anslist.append("W")
                else:
                    anslist.append("S")
        else:
            if anslist[i] == "S":
                if anslist[i-1] == "S":
                    anslist.append("W")
                else:
                    anslist.append("S")
            else:
                anslist.append(anslist[i-1])
    else:
        if Slist[i] == "o":
            if anslist[-1] == "S":
                froflag = anslist[i-1]
            else:
                if anslist[i-1] == "S":
                    froflag = "W"
                else:
                    froflag = "S"
        else:
            if anslist[-1] == "S":
                if anslist[i-1] == "S":
                    froflag = "W"
                else:
                    froflag = "S"
            else:
                froflag = anslist[i-1]

if maeflag == anslist[-1] and froflag == anslist[0]:
    print("".join(anslist))
    flag = 1

anslist = []
maeflag = ""
froflag = ""
for i in range(N):
    if i == 0:
        anslist.append("S")
        if Slist[0] == "o":
            maeflag = "W"
        else:
            maeflag = "S"
    elif i == 1:
        anslist.append("W")
        if Slist[i] == "o":
            anslist.append("W")
        else:
            anslist.append("S")
    elif i < N-1:
        if Slist[i] == "o":
            if anslist[i] == "S":
                anslist.append(anslist[i-1])
            else:
                if anslist[i-1] == "S":
                    anslist.append("W")
                else:
                    anslist.append("S")
        else:
            if anslist[i] == "S":
                if anslist[i-1] == "S":
                    anslist.append("W")
                else:
                    anslist.append("S")
            else:
                anslist.append(anslist[i-1])
    else:
        if Slist[i] == "o":
            if anslist[-1] == "S":
                froflag = anslist[i-1]
            else:
                if anslist[i-1] == "S":
                    froflag = "W"
                else:
                    froflag = "S"
        else:
            if anslist[-1] == "S":
                if anslist[i-1] == "S":
                    froflag = "W"
                else:
                    froflag = "S"
            else:
                froflag = anslist[i-1]
if maeflag == anslist[-1] and froflag == anslist[0] and flag == 0:
    print("".join(anslist))
    flag = 1
      
anslist = []
maeflag = ""
froflag = ""
for i in range(N):
    if i == 0:
        anslist.append("W")
        if Slist[0] == "o":
            maeflag = "W"
        else:
            maeflag = "S"
    elif i == 1:
        anslist.append("S")
        if Slist[i] == "o":
            anslist.append("W")
        else:
            anslist.append("S")
    elif i < N-1:
        if Slist[i] == "o":
            if anslist[i] == "S":
                anslist.append(anslist[i-1])
            else:
                if anslist[i-1] == "S":
                    anslist.append("W")
                else:
                    anslist.append("S")
        else:
            if anslist[i] == "S":
                if anslist[i-1] == "S":
                    anslist.append("W")
                else:
                    anslist.append("S")
            else:
                anslist.append(anslist[i-1])
    else:
        if Slist[i] == "o":
            if anslist[-1] == "S":
                froflag = anslist[i-1]
            else:
                if anslist[i-1] == "S":
                    froflag = "W"
                else:
                    froflag = "S"
        else:
            if anslist[-1] == "S":
                if anslist[i-1] == "S":
                    froflag = "W"
                else:
                    froflag = "S"
            else:
                froflag = anslist[i-1]

if maeflag == anslist[-1] and froflag == anslist[0] and flag == 0:
    print("".join(anslist))
    flag = 1
    
anslist = []
maeflag = ""
froflag = ""
for i in range(N):
    if i == 0:
        anslist.append("W")
        if Slist[0] == "o":
            maeflag = "S"
        else:
            maeflag = "W"
    elif i == 1:
        anslist.append("W")
        if Slist[i] == "o":
            anslist.append("S")
        else:
            anslist.append("W")
    elif i < N-1:
        if Slist[i] == "o":
            if anslist[i] == "S":
                anslist.append(anslist[i-1])
            else:
                if anslist[i-1] == "S":
                    anslist.append("W")
                else:
                    anslist.append("S")
        else:
            if anslist[i] == "S":
                if anslist[i-1] == "S":
                    anslist.append("W")
                else:
                    anslist.append("S")
            else:
                anslist.append(anslist[i-1])
    else:
        if Slist[i] == "o":
            if anslist[-1] == "S":
                froflag = anslist[i-1]
            else:
                if anslist[i-1] == "S":
                    froflag = "W"
                else:
                    froflag = "S"
        else:
            if anslist[-1] == "S":
                if anslist[i-1] == "S":
                    froflag = "W"
                else:
                    froflag = "S"
            else:
                froflag = anslist[i-1]

if maeflag == anslist[-1] and froflag == anslist[0] and flag == 0:
    print("".join(anslist))
    flag = 1
    
if flag == 0:
    print(-1)

Submission status: Accepted

Solution code:
N = int(input())
s = [1 if s=='o' else 0 for s in input()]

# 1:sheep, 0:wolf
def check(a,b):
  answer = [None]*N
  answer[0]=a
  answer[-1]=b
  for i in range(0,N-2):
    answer[i+1] = answer[i-1]^answer[i]^s[i]
  #print(answer)
  if answer[N-3]^answer[N-2]^s[N-2]==answer[N-1] and answer[N-2]^answer[N-1]^s[N-1]==answer[0]:
    return answer
  else:
    return False
  
for a,b in [(0,0),(1,0),(0,1),(1,1)]:
  x = check(a,b)
  if x:
    print(''.join(['S' if a==1 else 'W' for a in x]))
    break
else:
  print(-1)

Submission status: Accepted

Solution code:
def solve():
    n = int(input())
    s=input()
    s=[1 if i=='o' else -1 for i in s]
    ans=[0]*n
    ini=[(1, 1), (1, -1), (-1, 1), (-1, -1)]
    for i in ini:
        ans[0]=i[0]
        ans[1]=i[1]
        for j in range(2, n):
            ans[j]=ans[j-1]*ans[j-2]*s[j-1]
        if ans[n-1]*ans[0]*s[0]==ans[1] and ans[n-1]*ans[n-2]*s[n-1]==ans[0]:
            ans=['S' if i==1 else 'W' for i in ans]
            return ''.join(ans)
    return -1
print(solve())

Submission status: Accepted

Solution code:
# 入力
N = int(input())
s = input()
xs = [
    1 if c == 'o' else
    -1
    for c in s
]

# 動物1と動物2の種別を決め打ちで割り当てて、矛盾がないかを検証する
dp = {
    l: {
        r: [0 for _ in range(N + 2)]
        for r in (1, -1)
    }
    for l in (1, -1)
}
for l in (1, -1):
    for r in (1, -1):
        dp[l][r][0] = l
        dp[l][r][1] = r
        for i in range(2, N + 2):
            dp[l][r][i] = dp[l][r][i - 2] * dp[l][r][i - 1] * xs[(i - 1) % N]
ans = next(
    (
        ''.join(
            'S' if dp[l][r][i] == 1 else
            'W'
            for i in range(N)
        )
        for l in (1, -1)
        for r in (1, -1)
        if dp[l][r][N] == l and dp[l][r][N + 1] == r
    ),
    '-1'
)

# 出力
print(ans)

Submission status: Accepted

Solution code:
# 入力
N = int(input())
s = input()
xs = [
    1 if c == 'o' else
    -1
    for c in s
]

# 動物1と動物2の種別を決め打ちで割り当てて、矛盾がないかを検証する
dp = {
    l: {
        r: [0 for _ in range(N + 2)]
        for r in (1, -1)
    }
    for l in (1, -1)
}
for l in (1, -1):
    for r in (1, -1):
        dp[l][r][0] = l
        dp[l][r][1] = r
        for i in range(2, N + 2):
            dp[l][r][i] = dp[l][r][i - 2] * dp[l][r][i - 1] * xs[(i - 1) % N]


def f(l, r):
    return ''.join(
        'S' if dp[l][r][i] == 1 else
        'W'
        for i in range(N)
    )


ans = next(
    (
        f(l, r)
        for l in (1, -1)
        for r in (1, -1)
        if dp[l][r][N] == l and dp[l][r][N + 1] == r
    ),
    '-1'
)

# 出力
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=[s for s in input()]
def res(i,a,b):
    if S[i]=="o":
        if a==b:
            return "S"
        else:
            return "W"
    else:
        if a==b:
            return "W"
        else:
            return "S"
def check(a,b):
    ans=[""]*N
    ans[0]=a
    ans[1]=b
    for i in range(2,N):
        ans[i]=res(i-1,ans[i-2],ans[i-1])
    if ans[0]==res(N-1,ans[N-2],ans[N-1]) and ans[1]==res(0,ans[N-1],ans[0]):
        return True,ans
    else:
        return False,ans
flag=False
for a,b in [("S","S"),("S","W"),("W","S"),("W","W")]:
    R,ans=check(a,b)
    if R:
        print("".join(ans))
        flag=True
        break
if not flag:
    print(-1)

Submission status: Accepted

Solution code:
N = int(input())
s = list(input())

ansj = "NO"
L = [["W", "W"], ["W", "S"], ["S", "W"], ["S", "S"]]
for i in range(4):
	t = ""
	x = L[i][0]
	y = L[i][1]
	t += x + y
	for j in range(2, N):
		judge = 0
		if s[j - 1] == "x":
			judge += 1
		if y == "W":
			judge += 1
		if x == "W":
			judge += 1

		if judge % 2 == 0:
			z = "S"
		else:
			z = "W"
		t += z
		x, y = y, z

	#判定
	ans1 = 0
	if t[0] == "W":
		ans1 += 1
	if s[0] == "x":
		ans1 += 1
	if t[1] != t[-1]:
		ans1 += 1

	ans2 = 0
	if t[-1] == "W":
		ans2 += 1
	if s[-1] == "x":
		ans2 += 1
	if t[-2] != t[0]:
		ans2 += 1

	if ans1 % 2 == 0 and ans2 % 2 == 0:
		print(t)
		ansj = "YES"
		break

if ansj == "NO":
	print(-1)

Submission status: Accepted

Solution code:
a = int(input())
b = input()

t = ["SS","SW","WS","WW"]
l = []
for j in range(4):
  if t[j][0] == "S" and b[0] == "o":
    l.append("S" if t[j][1] == "S" else "W")
  elif t[j][0] == "S" and b[0] == "x":
    l.append("S" if t[j][1] == "W" else "W")
  elif t[j][0] == "W" and b[0] == "x":
    l.append("S" if t[j][1] == "S" else "W")
  elif t[j][0] == "W" and b[0] == "o":
    l.append("S" if t[j][1] == "W" else "W")
  for i in range(1,a):
    if t[j][i] == "S" and b[i] == "o":
      t[j]+="S" if t[j][i-1] == "S" else "W"
    elif t[j][i] == "S" and b[i] == "x":
      t[j]+="S" if t[j][i-1] == "W" else "W"
    elif t[j][i] == "W" and b[i] == "x":
      t[j]+="S" if t[j][i-1] == "S" else "W"
    elif t[j][i] == "W" and b[i] == "o":
      t[j]+="S" if t[j][i-1] == "W" else "W"
    else:
      t[j] = -1
      break
s = -1
if all(i == -1 for i in t):
  print(-1)
else:
  for j,k in enumerate(t):
    # print(j,k)
    # if k !=-1:
    #   if t[j][-1] == "S" and b[-1] == "o" and t[j][0] == "S":
    #     s = t[j]
    #   elif t[j][-1] == "S" and b[-1] == "x" and t[j][0] == "W":
    #     s = t[j]
    #   elif t[j][-1] == "W" and b[-1] == "x" and t[j][0] == "S":
    #     s = t[j]
    #   elif t[j][-1] == "W" and b[-1] == "o" and t[j][0] == "W":
    #     s = t[j]
    if k !=-1:
      if k[-1] ==  k[0] :
        if k[-2] ==l[j]:
          s = k
  if s == -1:print(-1)
  else:print(s[:-1])

Submission status: Accepted

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

def calc(st):
    l = 2
    while l<n:
        ed = (l-1)%n
        if (s[ed]=='o' and st[-1]=='S') or (s[ed]=='x' and st[-1]=='W'):
            st += st[-2]
        else:
            if st[-2] == 'S':
                st += 'W'
            else:
                st += 'S'
        l = len(st)
    
    if ((s[-1]=='o' and st[-1]=='S') or (s[-1]=='x' and st[-1]=='W')) and st[-2]!=st[0]:
        return -1
    elif ((s[-1]=='x'and st[-1]=='S')or(s[-1]=='o'and st[-1]=='W'))and st[-2]==st[0]:
        return -1

    if ((s[0]=='o' and st[0]=='S') or (s[0]=='x' and st[0]=='W')) and st[-1]!=st[1]:
        return -1
    elif ((s[0]=='x' and st[0]=='S') or (s[0]=='o' and st[0]=='W'))and st[-1]==st[1]:
        return -1
    return st

for st in ['SS','SW','WS','WW']:
    res = calc(st)
    if res!=-1:
        print(res)
        exit(0)
print(-1)

Submission status: Accepted

Solution code:
import re
n=int(input())
s=input()
for i in range(4):
  u=format(i,'02b')
  a=('S' if u[0]=='0' else 'W')
  b=('S' if u[1]=='0' else 'W')
  t=['?']*n
  t[0]=a
  t[1]=b
  for j in range(1,n+2):
    if s[j%n]=='o' and t[j%n]=='S' or s[j%n]=='x' and t[j%n]=='W':
      t[(j+1)%n]=t[(j-1)%n]
    else:
      t[(j+1)%n]=('S' if t[(j-1)%n]=='W' else 'W')
  if t[0]==a and t[1]==b:
    print(re.sub("[^SW]","",str(t)))
    exit()
print(-1)

Submission status: Accepted

Solution code:
import re
n=int(input())
s=input()
for i in range(4):
  u=format(i,'02b')
  a=('S' if u[0]=='0' else 'W')
  b=('S' if u[1]=='0' else 'W')
  t=['?']*n
  t[0]=a
  t[1]=b
  for j in range(1,n+2):
    if s[j%n]=='o' and t[j%n]=='S' or s[j%n]=='x' and t[j%n]=='W':
      t[(j+1)%n]=t[(j-1)%n]
    else:
      t[(j+1)%n]=('S' if t[(j-1)%n]=='W' else 'W')
  if t[0]==a and t[1]==b:
    print(re.sub("[^SW]","",str(t)))
    exit()
print(-1)
exit()

Submission status: Accepted

Solution code:
n = int(input())
S = input()
def check(start_now,start_before):
    now = start_now
    before = start_before
    ans = ""
    for i in S:
        ans += now
        if i == "o" and now == "S":
            if before == "S":
                now = "S"
                before = "S"
            else:
                now = "W"
                before = "S"
        elif i == "o" and now == "W":
            if before == "S":
                now = "W"
                before = "W"
            else:
                now = "S"
                before = "W"
        elif i == "x" and now == "S":
            if before == "S":
                now = "W"
                before = "S"
            else:
                now = "S"
                before = "S"
        elif i == "x" and now == "W":
            if before == "S":
                now = "S"
                before = "W"
            else:
                now = "W"
                before = "W"
    if now == start_now and before == start_before:
        print(ans)
        exit()

cheak_list = [["S","S"],["S","W"],["W","S"],["W","W"]]
for c in cheak_list:
    start_now, start_before = c
    check(start_now,start_before)
print(-1)

Submission status: Accepted

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

def parse_ox(c):
    if c == "o":
        return 0
    elif c == "x":
        return 1

def select_good_c(past, ox):
    if past == "SS":
        return "S" if ox == "o" else "W"
    elif past == "SW":
        return "W" if ox == "o" else "S"
    elif past == "WS":
        return "W" if ox == "o" else "S"
    elif past == "WW":
        return "S" if ox == "o" else "W"

val = ""
start = [["SSS", "WSW", "WWS", "SWW"], ["SSW", "WSS", "SWS", "WWW"]] 
for val in start[parse_ox(s[1])]:
    for i in range(2,n):
        val += select_good_c(val[-2:], s[i])
    if val[0] == val[-1] and select_good_c(val[-2:], s[0]) == val[1]:
        print(val[:-1])
        exit()
print(-1)