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()

res = 'W'
if s[0] == 'o':
    res += 'S'
    for i in range(2,n+1):
        if s[i-1] == 'o':
            if res[i-1] == 'S':
                t = res[i-2]
            else:
                if res[i-2] == 'S':
                    t = 'W'
                else:
                    t = 'S'
        else:
            if res[i - 1] == 'S':
                if res[i-2] == 'S':
                    t = 'W'
                else:
                    t = 'S'
            else:
                t = res[i - 2]
        res += t
    if res[-1] == 'W' and res[-2] == 'W':
        print(res[:-1])
        exit()
res = 'W'
if s[0] == 'o':
    res += 'W'
    for i in range(2,n+1):
        if s[i-1] == 'o':
            if res[i-1] == 'S':
                t = res[i-2]
            else:
                if res[i-2] == 'S':
                    t = 'W'
                else:
                    t = 'S'
        else:
            if res[i - 1] == 'S':
                if res[i-2] == 'S':
                    t = 'W'
                else:
                    t = 'S'
            else:
                t = res[i - 2]
        res += t
    if res[-1] == 'W' and res[-2] == 'S':
        print(res[:-1])
        exit()
res = 'W'
if s[0] == 'x':
    res += 'S'
    for i in range(2,n+1):
        if s[i-1] == 'o':
            if res[i-1] == 'S':
                t = res[i-2]
            else:
                if res[i-2] == 'S':
                    t = 'W'
                else:
                    t = 'S'
        else:
            if res[i - 1] == 'S':
                if res[i-2] == 'S':
                    t = 'W'
                else:
                    t = 'S'
            else:
                t = res[i - 2]
        res += t
    if res[-1] == 'W' and res[-2] == 'S':
        print(res[:-1])
        exit()
res = 'W'
if s[0] == 'x':
    res += 'W'
    for i in range(2,n+1):
        if s[i-1] == 'o':
            if res[i-1] == 'S':
                t = res[i-2]
            else:
                if res[i-2] == 'S':
                    t = 'W'
                else:
                    t = 'S'
        else:
            if res[i - 1] == 'S':
                if res[i-2] == 'S':
                    t = 'W'
                else:
                    t = 'S'
            else:
                t = res[i - 2]
        res += t
    if res[-1] == 'W' and res[-2] == 'W':
        print(res[:-1])
        exit()

res = 'S'
if s[0] == 'o':
    res += 'S'
    for i in range(2,n+1):
        if s[i-1] == 'o':
            if res[i-1] == 'S':
                t = res[i-2]
            else:
                if res[i-2] == 'S':
                    t = 'W'
                else:
                    t = 'S'
        else:
            if res[i - 1] == 'S':
                if res[i-2] == 'S':
                    t = 'W'
                else:
                    t = 'S'
            else:
                t = res[i - 2]
        res += t
    if res[-1] == 'S' and res[-2] == 'S':
        print(res[:-1])
        exit()
res = 'S'
if s[0] == 'o':
    res += 'W'
    for i in range(2,n+1):
        if s[i-1] == 'o':
            if res[i-1] == 'S':
                t = res[i-2]
            else:
                if res[i-2] == 'S':
                    t = 'W'
                else:
                    t = 'S'
        else:
            if res[i - 1] == 'S':
                if res[i-2] == 'S':
                    t = 'W'
                else:
                    t = 'S'
            else:
                t = res[i - 2]
        res += t
    if res[-1] == 'S' and res[-2] == 'W':
        print(res[:-1])
        exit()
res = 'S'
if s[0] == 'x':
    res += 'S'
    for i in range(2,n+1):
        if s[i-1] == 'o':
            if res[i-1] == 'S':
                t = res[i-2]
            else:
                if res[i-2] == 'S':
                    t = 'W'
                else:
                    t = 'S'
        else:
            if res[i - 1] == 'S':
                if res[i-2] == 'S':
                    t = 'W'
                else:
                    t = 'S'
            else:
                t = res[i - 2]
        res += t
    if res[-1] == 'S' and res[-2] == 'W':
        print(res[:-1])
        exit()
res = 'S'
if s[0] == 'x':
    res += 'W'
    for i in range(2,n+1):
        if s[i-1] == 'o':
            if res[i-1] == 'S':
                t = res[i-2]
            else:
                if res[i-2] == 'S':
                    t = 'W'
                else:
                    t = 'S'
        else:
            if res[i - 1] == 'S':
                if res[i-2] == 'S':
                    t = 'W'
                else:
                    t = 'S'
            else:
                t = res[i - 2]
        res += t
    if res[-1] == 'S' and res[-2] == 'S':
        print(res[:-1])
        exit()

print(-1)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
s = LS2()
for i in range(N):
    if s[i] == 'o':
        s[i] = 0
    else:
        s[i] = 1

for a,b in [(0,0),(0,1),(1,0),(1,1)]:  # 1,2番目の動物で全探索
    A = [0]*N
    A[0] = a
    A[1] = b
    for i in range(2,N):
        A[i] = A[i-2] ^ A[i-1] ^ s[i-1]
    if A[0] == A[-2] ^ A[-1] ^ s[-1] and A[1] == A[-1] ^ A[0] ^ s[0]:
        A = ['S' if A[i] == 0 else 'W' for i in range(N)]
        print(''.join(A))
        exit()

print(-1)

Submission status: Accepted

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


for s in ['SS', 'SW', 'WS', 'WW']:
    ss = s
    jdg = False
    for i in range(1, N):
        if S[i] == 'o':
            if ss[i] == 'S':
                ss += ss[i - 1]
            else:
                if ss[i - 1] == 'W': ss += 'S'
                else: ss += 'W'
        else:
            if ss[i] == 'S':
                if ss[i - 1] == 'W': ss += 'S'
                else: ss += 'W'
            else:
                ss += ss[i - 1]
    if ss[N] == ss[0]:
        if S[0] == 'o':
            if (ss[0] == 'S' and ss[N-1] == ss[1]) or (ss[0] == 'W' and ss[N-1] != ss[1]):
                jdg = True
                break
        else:
            if (ss[0] == 'S' and ss[N-1] != ss[1]) or (ss[0] == 'W' and ss[N-1] == ss[1]):
                jdg = True
                break
print(ss[:-1] if jdg else -1)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    S = readline().strip()

    ans = -1
    for last, first in ((0, 0), (0, 1), (1, 0), (1, 1)):
        vec = [0] * N
        vec[-1] = last
        vec[0] = first
        for i in range(N):
            if vec[i] == 0:
                if S[i] == 'o':
                    vec[(i + 1) % N] = vec[i - 1]
                else:
                    vec[(i + 1) % N] = 1 - vec[i - 1]
            else:
                if S[i] == 'o':
                    vec[(i + 1) % N] = 1 - vec[i - 1]
                else:
                    vec[(i + 1) % N] = vec[i - 1]

        if vec[-1] == last and vec[0] == first:
            ans = ''.join('S' if a == 0 else 'W' for a in vec)
            break

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
S=input()
for t in ["SS", "SW", "WS", "WW"]:
  for i in S[1:-1]:
    if t[-1] == "S":
      if i == "o": t+=t[-2]
      else: t += "S" if t[-2] == "W" else "W"
    else:
      if i == "x": t += t[-2]
      else: t += "S" if t[-2] == "W" else "W"

    if t[0] == "S":
      if S[0] == "o": f = t[-1] == t[1]
      else: f = t[-1] != t[1]
    else:
      if S[0] == "x": f = t[-1] == t[1]
      else: f = t[-1] != t[1]
 
    if t[-1] == "S":
      if S[-1] == "o": g = t[-2] == t[0]
      else: g = t[-2] != t[0]
    else:
      if S[-1] == "x": g = t[-2] == t[0]
      else: g = t[-2] != t[0]
 
  if f and g:
    print(t)
    exit()

print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

dic={'o':lambda s:1-(s[1]^s[0]), 'x':lambda s:s[1]^s[0]}
def mknseq(ox,ld):
    for x in ld:
        x.append(dic[ox]((x[-2],x[-1])))
def main():
    N=int(sys.stdin.readline().strip())
    s=list(sys.stdin.readline().strip())
    # ans=[deque([x,y]) for x in range(2) for y in range(2)]
    ans=[[x,y] for x in range(2) for y in range(2)]
    for x in range(N):
        mknseq(s[x],ans)
    # print(ans)
    for x in ans:
        if x[0]==x[-2] and x[1]==x[-1]:
            return print(''.join([['W','S'][i] for i in x])[1:-1])
    print(-1)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

dic={'o':lambda s:1-(s[1]^s[0]), 'x':lambda s:s[1]^s[0]}
def mknseq(ox,ld):
    for x in ld:
        x.append(dic[ox]((x[-2],x[-1])))
def main():
    N=int(sys.stdin.readline().strip())
    s=list(sys.stdin.readline().strip())
    ans=[deque([x,y]) for x in range(2) for y in range(2)]
    for x in range(N):
        mknseq(s[x],ans)
    # print(ans)
    for x in ans:
        if x[0]==x[-2] and x[1]==x[-1]:
            return print(''.join([['W','S'][i] for i in x])[1:-1])
    print(-1)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

dic={'o':lambda s:1-(s[1]^s[0]), 'x':lambda s:s[1]^s[0]}
def mknseq(ox,ld):
    for x in ld:
        x.append(dic[ox]([x[-2],x[-1]]))
def main():
    N=int(sys.stdin.readline().strip())
    s=list(sys.stdin.readline().strip())
    ans=[deque([x,y]) for x in range(2) for y in range(2)]
    for x in range(N):
        mknseq(s[x],ans)
    ans=[list(x) for x in ans]
    # print(ans)
    for x in ans:
        if x[:2]==x[-2:]:
            return print(''.join([['W','S'][i] for i in x[1:-1]]))
    print(-1)

if __name__=='__main__':
    main()

Submission status: Accepted

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

animal = ["S", "W"]

start = [[0, 0], [0, 1], [1, 0], [1, 1]]#最初の2つを指定

for i, j in start:
  ans = [-1] * N
  ans[0] = i
  ans[1] = j
  p = 0
  for k in range(N - 1):
    #print(ans)
    if p == 0:
      if k == 0:
        if S[k] == "o":
          if ans[k] == 0:
            ans[-1] = ans[1]
          else:
            ans[-1] = 1 - ans[1]
        else:
          if ans[k] == 0:
            ans[-1] = 1 - ans[1]
          else:
            ans[-1] = ans[1]
      else:
        if S[k] == "o":
          if ans[k] == 0:
            now = ans[k - 1]
            if ans[k + 1] == 1 - now:
              p = 1
            else:
              ans[k + 1] = now
          else:
            now = 1 - ans[k - 1]
            if ans[k + 1] == 1 - now:
              p = 1
            else:
              ans[k + 1] = now            
        else:
          if ans[k] == 0:
            now = 1 - ans[k - 1]
            if ans[k + 1] == 1 - now:
              p = 1
            else:
              ans[k + 1] = now
          else:
            now = ans[k - 1]
            if ans[k + 1] == 1 - now:
              p = 1
            else:
              ans[k + 1] = now
  
  #N == 3の時に備えて
  if ans[-1] == 0:
    if S[-1] == "o":
      if ans[-2] != ans[0]:
        p = 1
    else:
      if ans[-2] == ans[0]:
        p = 1
  else:
    if S[-1] == "o":
      if ans[-2] == ans[0]:
        p = 1
    else:
      if ans[-2] != ans[0]:
        p = 1
  
  if p == 0:
    #print(ans)  
    for i in range(N):
      if ans[i] == 0:
        print("S", end = "")
      else:
        print("W", end = "")
    quit()
    
print(-1)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
ch=['S','W']


for c1 in range(2):
    for c0 in range(2):
        if (ch[c1]=='S' and s[1]=='o') or (ch[c1]=='W' and s[1]=='x'):
            ans=ch[c0]+ch[c1]+ch[c0]
        else:
            ans=ch[c0]+ch[c1]+ch[(c0+1)%2]
        
        i=2

        while i<n-1:
            if (ans[-1]=='S' and s[i]=='o') or (ans[-1]=='W' and s[i]=='x'):
                ans+=ans[-2]
            else:
                ans+='W' if ans[-2]=='S' else 'S'
            i+=1
        
        for i in range(n):
            bc=ans[(i-1+n)%n]
            ac=ans[(i+1)%n]

            if (ans[i]=='S' and s[i]=='o') or (ans[i]=='W' and s[i]=='x'):
                if bc!=ac:
                    break
            else:
                if bc==ac:
                    break
        else:
            print(ans)
            exit(0)

print(-1)

Submission status: Accepted

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

lst = ["SW", "WS", "SS", "WW"]
ans = []

for tmp in lst:
    for i in range(1, N-1):
        if(s[i] == "o"):
            if(tmp[i] == "S"):
                tmp += tmp[i-1]
            else:
                if(tmp[i-1] == "S"):
                    tmp += "W"
                else:
                    tmp += "S"
        else:
            if(tmp[i] == "W"):
                tmp += tmp[i-1]
            else:
                if(tmp[i-1] == "S"):
                    tmp += "W"
                else:
                    tmp += "S"

    ans.append(tmp)

for st in ans:
    flg = True
    if(s[0] == "o"):
        if(st[0] == "S"):
            if(st[-1] != st[1]):
                flg = False
        else:
            if(st[-1] == st[1]):
                flg = False
    else:
        if(st[0] == "S"):
            if(st[-1] == st[1]):
                flg = False
        else:
            if(st[-1] != st[1]):
                flg = False
    if(s[N-1] == "o"):
        if(st[N-1] == "S"):
            if(st[N-2] != st[0]):
                flg = False
        else:
            if(st[N-2] == st[0]):
                flg = False
    else:
        if(st[N-1] == "S"):
            if(st[N-2] == st[0]):
                flg = False
        else:
            if(st[N-2] != st[0]):
                flg = False
    if(flg):
        print(st)
        sys.exit()
print(-1)

Submission status: Accepted

Solution code:
N = int(input())
s = list(input())
s = s * 2
q = [[True,True],[True,False],[False,True],[False,False]]
p = []
ans = []
for k in range(4):
    p = q[k]
    for i in range(N*2-2):
        if p[i + 1]:
            if s[i + 1] == "o":
                p.append(p[i])
            else:
                p.append(not p[i])
        else:
            if s[i + 1] == "o":
                p.append(not p[i])
            else:
                p.append(p[i])
    if p[0:N-1] == p[N:N*2-1]:
        for i in range(N):
            if p[i]:
                ans.append("S")
            else:
                ans.append("W")
        print("".join(ans))
        break
    if k == 3:
        print(-1)

Submission status: Accepted

Solution code:
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial,sqrt
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
s=SI()
def nex(i):
    if i==n-1:
        i=-1
    if lis[i]==1:
        if s[i]=="o":
            if lis[i-1]==1:
                lis[i+1]=1
            else:
                lis[i+1]=0
        else:
            if lis[i-1]==1:
                lis[i+1]=0
            else:
                lis[i+1]=1
    else:
        if s[i]=="o":
            if lis[i-1]==1:
                lis[i+1]=0
            else:
                lis[i+1]=1
        else:
            if lis[i-1]==0:
                lis[i+1]=0
            else:
                lis[i+1]=1

for i in product([0,1],repeat=2):
    lis=[0 for i in range(n)]
    lis[0],lis[1]=i[0],i[1]
    for i in range(1,n-1):
        nex(i)
    #print(lis)
    x=lis[0]
    y=lis[1]
    nex(n-1)
    nex(0)
    if x==lis[0] and y==lis[1]:
        for i in range(n):
            if lis[i]==1:
                print("S",end="")
            else:
                print("W",end="")
        sys.exit()
print(-1)

Submission status: Accepted

Solution code:
import sys
from enum import Enum

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from itertools import product
    n = int(readline())
    s = input()

    for a, b in product(("S", "W"), repeat=2):
        kinds = [""] * n
        kinds[0] = a
        kinds[1] = b

        for i in range(1, n - 1):
            if kinds[i] is "S":
                if s[i] == "o":
                    kinds[i + 1] = kinds[i - 1]
                else:
                    if kinds[i - 1] == "S":
                        kinds[i + 1] = "W"
                    else:
                        kinds[i + 1] = "S"
            else:
                if s[i] == "o":
                    if kinds[i - 1] == "S":
                        kinds[i + 1] = "W"
                    else:
                        kinds[i + 1] = "S"
                else:
                    kinds[i + 1] = kinds[i - 1]
        ff = (s[n - 1] == "o") ^ (kinds[n - 1] == "W")
        fs = (s[0] == "o") ^ (kinds[0] == "W")
        f1 = False
        f2 = False
        if ff and (kinds[n - 2] == kinds[0]):
            f1 = True
        if not ff and (kinds[n - 2] != kinds[0]):
            f1 = True
        if fs and (kinds[n - 1] == kinds[1]):
            f2 = True
        if not fs and (kinds[n - 1] != kinds[1]):
            f2 = True

        if f1 and f2:
            res = "".join(kinds)
            print(res)
            sys.exit()
    print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(readline())
    s = input()

    if s[1] == "o":
        first = ((True, True, True),
                 (False, True, False),
                 (True, False, False),
                 (False, False, True))
    else:
        first = ((True, True, False),
                 (False, True, True),
                 (True, False, True),
                 (False, False, False))

    for a, b, c in first:
        kinds = [None] * (n + 1)
        kinds[1] = b
        kinds[0] = a
        kinds[2] = c

        for i in range(2, n):
            if kinds[i]:
                if s[i] == "o":
                    kinds[i + 1] = kinds[i - 1]
                else:
                    kinds[i + 1] = not kinds[i - 1]
            else:
                if s[i] == "o":
                    kinds[i + 1] = not kinds[i - 1]
                else:
                    kinds[i + 1] = kinds[i - 1]

        res = ""
        flag = True
        for i in range(n):
            left = kinds[(i - 1) % n]
            right = kinds[(i + 1) % n]
            res += "S" if kinds[i] else "W"
            if (s[i] == "o" and kinds[i]) or (s[i] == "x" and not kinds[i]):
                if left != right:
                    flag = False
                    break
            else:
                if left == right:
                    flag = False
                    break
        if flag:
            print(res)
            sys.exit()

    print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())

s=list(input())

memo_ss = ['S','S']
memo_sw = ['S','W']
memo_ws = ['W','S']
memo_ww = ['W','W']

def check(memo_ss):
    for i in range(1,n):
        if s[i] == 'o' :
            if memo_ss[i] == 'S':
                if memo_ss[i-1] == 'S':
                    memo_ss.append('S')
                elif memo_ss[i-1] == 'W':
                    memo_ss.append('W')
            elif memo_ss[i] == 'W':
                if memo_ss[i-1] == 'S':
                    memo_ss.append('W')
                elif memo_ss[i-1] == 'W':
                    memo_ss.append('S')
        elif s[i] == 'x' :
            if memo_ss[i] == 'S':
                if memo_ss[i-1] == 'S':
                    memo_ss.append('W')
                elif memo_ss[i-1] == 'W':
                    memo_ss.append('S')
            elif memo_ss[i] == 'W':
                if memo_ss[i-1] == 'S':
                    memo_ss.append('S')
                elif memo_ss[i-1] == 'W':
                    memo_ss.append('W')
    return memo_ss

memo_ss = check(memo_ss)
memo_sw = check(memo_sw)
memo_ws = check(memo_ws)
memo_ww = check(memo_ww)

for memo in [memo_ss,memo_sw,memo_ws,memo_ww]:
    if memo[0] == memo[-1]:
        if s[0] == 'o':
            if memo[0] == 'S' and memo[1] == memo[n-1]:
                print(''.join(map(str,memo[:n])))
                exit()
            elif memo[0] == 'W' and memo[1] != memo[n-1]:
                print(''.join(map(str,memo[:n])))
                exit()
        elif s[0] == 'x':
                if memo[0] == 'S' and memo[1] != memo[n-1]:
                    print(''.join(map(str,memo[:n])))
                    exit()
                elif memo[0] == 'W' and memo[1] == memo[n-1]:
                    print(''.join(map(str,memo[:n])))
                    exit()
print(-1)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = input()
    M = [{'o': 0, 'x': 1}, {'o': 1, 'x': 0}]
    for s1, sn in [(0, 0), (0, 1), (1, 0), (1, 1)]:
        T = [s1]
        p, pp = s1, sn
        for s in S:
            pp, p = p, M[p ^ pp][s]
            T.append(p)
        if (s1, sn) == (p, pp):
            return T[:-1]
    return None

T = main()
if not T:
    print(-1)
else:
    print(''.join('S' if s == 0 else 'W' for s in T))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    s = input()
    #0 sheep 1 wolf
    for i in [[0,0],[0,1],[1,0],[1,1]]:
        t = i[:]
        for j in s[1:]:
            if t[-1] == 0:
                if j == 'o':
                    t.append(t[-2])
                else:
                    t.append(1-t[-2])
            elif j == 'o':
                t.append(1-t[-2])
            else:
                t.append(t[-2])
        if t[-1] == t[0]:
            if s[0] == 'o' and t[0] == 0 and t[1] != t[-2]:
                continue
            if s[0] == 'o' and t[0] == 1 and t[1] == t[-2]:
                continue
            if s[0] == 'x' and t[0] == 0 and t[1] == t[-2]:
                continue
            if s[0] == 'x' and t[0] == 1 and t[1] != t[-2]:
                continue
            print(''.join(['S' if i == 0 else 'W' for i in t[:-1]]))
            return
    print(-1)
    return
main()

Submission status: Accepted

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

P = [
    ['S', 'S'],['S', 'W'],
    ['W', 'S'],['W', 'W']
]

if S[0] == 'o':
    n1 = ['S','W','W','S']
else:
    n1 = ['W','S','S','W']

for idx, p in enumerate(P):
    for i in range(1, n-1):
        if S[i] == 'o':
            if p[i] == 'S':
                p.append(p[i-1])
            else:
                p.append('W' if p[i-1] == 'S' else 'S')
        else:
            if p[i] == 'S':
                p.append('W' if p[i-1] == 'S' else 'S')
            else:
                p.append(p[i-1])
    if n1[idx] == p[-1]:
        if  (S[-1] == 'o' and n1[idx] == 'S' and p[0] == p[-2]) or\
            (S[-1] == 'o' and n1[idx] == 'W' and p[0] != p[-2]) or\
            (S[-1] == 'x' and n1[idx] == 'W' and p[0] == p[-2]) or\
            (S[-1] == 'x' and n1[idx] == 'S' and p[0] != p[-2]):
                print(''.join(p))
                break
else:
    print(-1)

Submission status: Accepted

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

assignable = False

for k in range(4):
    res = [None for _ in range(N)]
    res[0] = k % 2
    res[-1] = k // 2
    for i in range(N - 2):
        if S[i] == 'o':
            if res[i] == 0:
                res[i + 1] = res[i - 1]
            else:
                res[i + 1] = 1 - res[i - 1]
        else:
            if res[i] == 0:
                res[i + 1] = 1 - res[i - 1]
            else:
                res[i + 1] = res[i - 1]
    if S[-2] == 'o':
        if res[-2] == 0:
            if res[-1] != res[-3]:
                continue
        else:
            if res[-1] != 1 - res[-3]:
                continue
    else:
        if res[-2] == 0:
            if res[-1] != 1 - res[-3]:
                continue
        else:
            if res[-1] != res[-3]:
                continue
    if S[-1] == 'o':
        if res[-1] == 0:
            if res[0] == res[-2]:
                assignable = True
        else:
            if res[0] == 1 - res[-2]:
                assignable = True
    else:
        if res[-1] == 0:
            if res[0] == 1 - res[-2]:
                assignable = True
        else:
            if res[0] == res[-2]:
                assignable = True
    if assignable:
        for i in range(N):
            if res[i]:
                print('W', end='')
            else:
                print('S', end='')
        break
else:
    print(-1)

Submission status: Accepted

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

X = [''] * (N + 1)
X[0] = 'S'
X[1] = 'S'
for i in range(1, N):
    if X[i] == 'S':
        if S[i] == 'o':
            X[i + 1] = X[i - 1]
        else:
            if X[i - 1] == 'S':
                X[i + 1] = 'W'
            else:
                X[i + 1] = 'S'
    else:
        if S[i] == 'x':
            X[i + 1] = X[i - 1]
        else:
            if X[i - 1] == 'S':
                X[i + 1] = 'W'
            else:
                X[i + 1] = 'S'
if X[-1] == 'S':
    if (X[-2] == 'S' and S[0] == 'o') or (X[-2] == 'W' and S[0] == 'x'):
        X.pop()
        for x in X:
            print(x, end='')
        print('')
        sys.exit()

X = [''] * (N + 1)
X[0] = 'S'
X[1] = 'W'
for i in range(1, N):
    if X[i] == 'S':
        if S[i] == 'o':
            X[i + 1] = X[i - 1]
        else:
            if X[i - 1] == 'S':
                X[i + 1] = 'W'
            else:
                X[i + 1] = 'S'
    else:
        if S[i] == 'x':
            X[i + 1] = X[i - 1]
        else:
            if X[i - 1] == 'S':
                X[i + 1] = 'W'
            else:
                X[i + 1] = 'S'
if X[-1] == 'S':
    if (X[-2] == 'S' and S[0] == 'x') or (X[-2] == 'W' and S[0] == 'o'):
        X.pop()
        for x in X:
            print(x, end='')
        print('')
        sys.exit()

X = [''] * (N + 1)
X[0] = 'W'
X[1] = 'S'
for i in range(1, N):
    if X[i] == 'S':
        if S[i] == 'o':
            X[i + 1] = X[i - 1]
        else:
            if X[i - 1] == 'S':
                X[i + 1] = 'W'
            else:
                X[i + 1] = 'S'
    else:
        if S[i] == 'x':
            X[i + 1] = X[i - 1]
        else:
            if X[i - 1] == 'S':
                X[i + 1] = 'W'
            else:
                X[i + 1] = 'S'
if X[-1] == 'W':
    if (X[-2] == 'S' and S[0] == 'x') or (X[-2] == 'W' and S[0] == 'o'):
        X.pop()
        for x in X:
            print(x, end='')
        print('')
        sys.exit()

X = [''] * (N + 1)
X[0] = 'W'
X[1] = 'W'
for i in range(1, N):
    if X[i] == 'S':
        if S[i] == 'o':
            X[i + 1] = X[i - 1]
        else:
            if X[i - 1] == 'S':
                X[i + 1] = 'W'
            else:
                X[i + 1] = 'S'
    else:
        if S[i] == 'x':
            X[i + 1] = X[i - 1]
        else:
            if X[i - 1] == 'S':
                X[i + 1] = 'W'
            else:
                X[i + 1] = 'S'
if X[-1] == 'W':
    if (X[-2] == 'S' and S[0] == 'o') or (X[-2] == 'W' and S[0] == 'x'):
        X.pop()
        for x in X:
            print(x, end='')
        print('')
        sys.exit()

print('-1')