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()
start = ["WW","SS","WS","SW"]
for i in start:
    now = i
    for j in range(2,n):
        if now[j-1] == "S":
            if s[j-1] == "o":
                if now[j-2] == "S":
                    now += "S"
                elif now[j-2] == "W":
                    now += "W"
            elif s[j-1] == "x":
                if now[j-2] == "S":
                    now += "W"
                elif now[j-2] == "W":
                    now += "S"
        elif now[j-1] == "W":
            if s[j-1] == "o":
                if now[j-2] == "S":
                    now += "W"
                elif now[j-2] == "W":
                    now += "S"
            elif s[j-1] == "x":
                if now[j-2] == "S":
                    now += "S"
                elif now[j-2] == "W":
                    now += "W"
    if now[0] == "S":
        if s[0] == "o":
            if now[1] != now[-1]:
                continue
        elif s[0] == "x":
            if now[1] == now[-1]:
                continue
    elif now[0] == "W":
        if s[0] == "o":
             if now[1] == now[-1]:
                 continue
        elif s[0] == "x":
            if now[1] != now[-1]:
                continue
            
    if now[-1] == "S":
        if s[-1] == "o":
            if now[0] == now[-2]:
                print(now)
                exit()
        elif s[-1] == "x":
            if now[0] != now[-2]:
                print(now)
                exit()
    elif now[-1] == "W":
        if s[-1] == "o":
            if now[0] != now[-2]:
                print(now)
                exit()
        elif s[-1] == "x":
            if now[0] == now[-2]:
                print(now)
                exit()
print(-1)

Submission status: Accepted

Solution code:
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    def check(m):
        for bf, c, af, ss in zip(m, m[1:], m[2:], s):
            if ss == 'o':
                if (c == 'S' and bf != af) or (c == 'W' and bf == af):
                    return False
            else:
                if (c == 'S' and bf == af) or (c == 'W' and bf != af):
                    return False
        return True

    n = int(readline())
    s = readline().rstrip().decode()
    flag = {'S': 'W', 'W': 'S'}
    for m in ('SS', 'SW', 'WS', 'WW'):
        for i, ss in enumerate(s[1:-1]):
            if ss == 'o':
                if m[i + 1] == 'S':
                    m += m[i]
                else:
                    m += flag[m[i]]
            else:
                if m[i + 1] == 'S':
                    m += flag[m[i]]
                else:
                    m += m[i]
        if check(m[-1] + m + m[0]):
            print(m)
            break
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N = ini()
S = ins()


def flip(x):
    if x == "S":
        return "W"
    else:
        return "S"


def solve():
    for p in ["SS", "SW", "WS", "WW"]:
        buf = list(p)
        for i in range(1, N):
            if (buf[i] == "S" and S[i] == "o") or (buf[i] == "W" and S[i] == "x"):
                buf.append(buf[i - 1])
            else:
                buf.append(flip(buf[i - 1]))
        assert len(buf) == N + 1
        if buf[0] != buf[-1]:
            continue
        buf.pop()
        if buf[1] == buf[-1]:
            if (buf[0] == "S" and S[0] == "x") or (buf[0] == "W" and S[0] == "o"):
                continue
        else:
            if (buf[0] == "S" and S[0] == "o") or (buf[0] == "W" and S[0] == "x"):
                continue
        return "".join(buf)
    return -1


print(solve())

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
s = input()
t = []
for i in range(n):
    if s[i] == 'o':
        t.append(0)
    else:
        t.append(1)
def chk():
    if res[n-1] ^ t[n-1] != res[0] ^ res[n-2]:
        return False
    if res[0] ^ t[0] != res[n-1] ^ res[1]:
        return False
    return True
for zero,one in itertools.product(range(2),repeat=2):
    # 0:S 1:W
    res = [0] * n
    res[0] = zero; res[1] = one
    for i in range(2,n):
        if res[i-1] == t[i-1]:
            res[i] = res[i-2]
        else:
            res[i] = res[i-2]^1
    if chk():
        ans = []
        for i in range(n):
            ans.append('W' if res[i] else 'S')
        print(''.join(ans))
        quit()
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()
check1 = [None] * n
check1[0] = 'S'
check1[1] = 'S'
check2 = [None] * n
check2[0] = 'S'
check2[1] = 'W'
check3 = [None] * n
check3[0] = 'W'
check3[1] = 'S'
check4 = [None] * n
check4[0] = 'W'
check4[1] = 'W'
def check(lst):
    for i in range(1,n):
        if lst[i] == 'S':
            if s[i] == 'o':
                if i + 1 == n:
                    if lst[0] != lst[i-1]:
                        return False, lst
                else:
                    lst[i+1] = lst[i-1]
            else:
                if i + 1 == n:
                    if lst[0] == lst[i-1]:
                        return False, lst
                else:
                    if lst[i-1] == 'S':
                        lst[i+1] = 'W'
                    else:
                        lst[i+1] = 'S'
        else:
            if s[i] == 'o':
                if i + 1 == n:
                    if lst[0] == lst[i-1]:
                        return False, lst
                else:
                    if lst[i-1] == 'S':
                        lst[i+1] = 'W'
                    else:
                        lst[i+1] = 'S'
            else:
                if i + 1 == n:
                    if lst[0] != lst[i-1]:
                        return False, lst
                else:
                    lst[i+1] = lst[i-1]
    else:
        if s[0] == 'o' and lst[0] == 'S':
            if lst[-1] != lst[1]:
                return False, lst
        elif s[0] == 'o' and lst[0] == 'W':
            if lst[-1] == lst[1]:
                return False, lst
        elif s[0] == 'x' and lst[0] == 'S':
            if lst[-1] == lst[1]:
                return False, lst
        elif s[0] == 'x' and lst[0] == 'W':
            if lst[-1] != lst[1]:
                return False, lst
        return True, lst

f1, check1 = check(check1)
if f1:
    print(''.join(check1))
    quit()
f2, check2 = check(check2)
if f2:
    print(''.join(check2))
    quit()
f3, check3 = check(check3)
if f3:
    print(''.join(check3))
    quit()
f4, check4 = check(check4)
if f4:
    print(''.join(check4))
    quit()
print(-1)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
lis = [[0, 0], [0, 1], [1, 0], [1, 1]]
for c in s:
    c = 0 if c=='o' else 1
    for li in lis:
        li.append(li[-1]^li[-2]^c)
for li in lis:
    if li[0]==li[-2] and li[1]==li[-1]:
        ans = ['W' if i else 'S' for i in li[1:-1]]
        print(''.join(ans))
        break
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    s=input()
    ans=["" for _ in range(N)]

    for i0,i1 in (("S","S"),("W","S"),("S","W"),("W","W")):
        f=0
        ans[0]=i0
        ans[1]=i1
        for i in range(2,N):
            #print(s[i-1],ans[i-1])
            if (s[i-1]=="o" and ans[i-1]=="S") :
                ans[i]=ans[i-2]
            elif (s[i-1]=="x" and ans[i-1]=="W"):
                ans[i]=ans[i-2]
            else:
                if ans[i-2]=="W": ans[i]="S"
                else:ans[i]="W"
        #print(ans)

        if (ans[-1]=="S" and s[-1]=="o" and ans[-2]==ans[0]) or (ans[-1]=="S" and s[-1]=="x" and ans[-2]!=ans[0]) or (ans[-1]=="W" and s[-1]=="o" and ans[-2]!=ans[0]) or (ans[-1]=="W" and s[-1]=="x" and ans[-2]==ans[0]):
            if (ans[0]=="S" and s[0]=="o" ) or (ans[0]=="W" and s[0]=="x"):
                if ans[-1]==ans[1]:
                    f=1
            else:
                if ans[-1]!=ans[1]:
                    f=1
        
        if f:
            print("".join(ans))
            return
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

def resolve():
    n = int(input())
    s = list(input())
    init = [["S","S"], ["S","W"], ["W","S"], ["W","W"]]
    def addsheep (prev, now):
        if s[now] == "o":
            if ans[now] == "S" and ans[prev] == "S":
                return "S"
            elif ans[now] == "S" and ans[prev] == "W":
                return "W"
            elif ans[now] == "W" and ans[prev] == "S":
                return "W"
            elif ans[now] == "W" and ans[prev] == "W":
                return "S"
        if s[now] == "x":
            if ans[now] == "S" and ans[prev] == "S":
                return "W"
            elif ans[now] == "S" and ans[prev] == "W":
                return "S"
            elif ans[now] == "W" and ans[prev] == "S":
                return "S"
            elif ans[now] == "W" and ans[prev] == "W":
                return "W"

    OK = False
    for i in init:
        ans = i
        for j in range(n-2):
            ans.append(addsheep(j, j+1))

        if addsheep(n-2, n-1) == ans[0] and addsheep(n-1,0) == ans[1]:
            OK = True
            break
    if OK:
        print("".join(ans))
    else:
        print(-1)
resolve()

Submission status: Accepted

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
import re

n = ii()
s = input()
s = s+s[0]
#最初2つがSS/SW/WS/WWの状態で、前から決めてく
#S=1,W=0
l = [[1,1],[1,0],[0,1],[0,0]]
'''
ss = [1,1]
sw = [1,0]
ws = [0,1]
ww = [0,0]
'''

def nextAnimal(lis,st):
    if st == 'o':
        lis.append(lis[-2]^(lis[-1]^1))
    else:
        lis.append(lis[-2]^(lis[-1]))
#    print(lis)


for i in s[1:]:
    for item in l:
        nextAnimal(item,i)

#print(l)
for item in l:
    if item[0] == item[-2] and item[1] == item[-1]:
        ans = ''
        for i in item[:n]:
            if i == 0:
                ans += 'W'
            else:
                ans += 'S'
        print(ans)
        exit()
print(-1)

Submission status: Accepted

Solution code:
N = int(input())
s = input().strip()
flag = 1
A = [0 for _ in range(N)]
for a in range(2):
    for b in range(2):
        A[0]=a
        A[1]=b
        for i in range(1,N-1):
            if A[i]==0 and s[i]=="o":
                A[i+1]=A[i-1]
            elif A[i]==0 and s[i]=="x":
                A[i+1]=1-A[i-1]
            elif A[i]==1 and s[i]=="o":
                A[i+1]=1-A[i-1]
            elif A[i]==1 and s[i]=="x":
                A[i+1]=A[i-1]
        if A[N-1]==0 and s[N-1]=="o":
            if A[0]==A[N-2]:
                flag = 0
            else:
                flag = 1
                continue
        elif A[N-1]==0 and s[N-1]=="x":
            if A[0]==1-A[N-2]:
                flag = 0
            else:
                flag = 1
                continue
        elif A[N-1]==1 and s[N-1]=="o":
            if A[0]==1-A[N-2]:
                flag = 0
            else:
                flag = 1
                continue
        elif A[N-1]==1 and s[N-1]=="x":
            if A[0]==A[N-2]:
                flag = 0
            else:
                flag =1
                continue
        if A[0]==0 and s[0]=="o":
            if A[1]==A[N-1]:
                flag = 0
            else:
                flag =1
                continue
        elif A[0]==0 and s[0]=="x":
            if A[1]==1-A[N-1]:
                flag = 0
            else:
                flag = 1
                continue
        elif A[0]==1 and s[0]=="o":
            if A[1]==1-A[N-1]:
                flag = 0
            else:
                flag = 1
                continue
        elif A[0]==1 and s[0]=="x":
            if A[1]==A[N-1]:
                flag = 0
            else:
                flag = 1
                continue
        if flag==0:
            B = []
            for i in range(N):
                if A[i]==0:
                    B.append("S")
                else:
                    B.append("W")
            break
    if flag==0:break
if flag==1:
    print(-1)
else:
    print("".join(B))

Submission status: Accepted

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

master = [["S","S"],["W","S"],["S","W"],["W","W"]]
for case in range(4):
  ans = master[case]
  for i in range(len(s)):
    if ans[-2] == "S" and ans[-1] == "S":
      if s[i] == "o":
        temp = "S"
      else:
        temp = "W"
    elif ans[-2] == "W" and ans[-1] == "S":
      if s[i] == "o":
        temp = "W"
      else:
        temp = "S"
    elif ans[-2] == "S" and ans[-1] == "W":
      if s[i] == "o":
        temp = "W"
      else:
        temp = "S" 
    else:
      if s[i] == "o":
        temp = "S"
      else:
        temp = "W"
    ans.append(temp)
#print(ans)
  if ans[0] != ans[-2] or ans[1] != ans[-1]:
    continue
  else:
    answer = ans[1:-1]
    t = "".join(answer)
    print(t)
    exit()
print(-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
# from collections import defaultdict, deque
# import math
# import copy
# from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 1000000007

def nt(n):
    if n == "1":
        return "0"
    else:
        return "1"

def check(seed, n, s):
    ans = seed
    for i in range(1, n):
        a, b = ans[-1], ans[-2]
        if int(s[i]) ^ int(b) == 0:
            ans.append(a)
        else:
            ans.append(nt(a))

    if ans[-1] != ans[0]:
        return []
    else:
        del(ans[-1])
        # print(ans)
        if int(s[0]) ^ int(ans[0]) == 0:
            if ans[-1] != ans[1]:
                return []
        else:
            if ans[-1] == ans[1]:
                return []

    return "".join(ans).replace("1", "S").replace("0", "W")

def solve():
    n = getN()
    S = getS()
    S = S.replace("o", "1").replace("x", "0")
    for seed in  [["1","1"], ["1","0"], ["0","1"], ["0","0"]]:
        ans = check(seed, n, S)
        if ans:
            print(ans)
            return

    print(-1)
    return

def main():
    n = getN()
    for _ in range(n):
        solve()
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
n = int(input())
s = input()
for ans in ('SS', 'SW', 'WS', 'WW'):
    for i in range(n - 1):
        if (s[i + 1] == 'o') ^ (ans[-1] == 'S'):
            if ans[-2] == 'S':
                ans += 'W'
            else:
                ans += 'S'
        else:
            ans += ans[-2]
    if ans[0] == ans[-1] and (((s[0] == 'o') ^ (ans[0] == 'S')) ^ (ans[1] == ans[-2])):
        print(ans[:-1])
        break
else:
    print(-1)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
def solve(x):
  global S,N
  for i in range(N-1):
    if (x[i+1]=='W')^(S[i+1]=='x'):
      x.append('S' if x[i]=='W' else 'W')
    else:
      x.append('S' if x[i]=='S' else 'W')
  if (x[0]=='W')^(S[0]=='x'):
    x.insert(0,'S' if x[1]=='W' else 'W')
  else:
    x.insert(0,'S' if x[1]=='S' else 'W')
  if x[:2]==x[-2:]:
    print(''.join(x[1:-1]))
    exit()

solve(list('SS'))
solve(list('SW'))
solve(list('WS'))
solve(list('WW'))
print(-1)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
mod = 10**9+7

N = i()
S = s()
a = 'S'
b = 'W'
kouho = [[a,a],[a,b],[b,a],[b,b]]
for a,b in kouho:
    S1 = [a,b]
    for i in range(1,N):
        if S[i] == 'o':
            if S1[i] == 'S':
                if S1[i-1] == 'S':
                    S1.append('S')
                else:
                    S1.append('W')
            else:
                if S1[i-1] == 'S':
                    S1.append('W')
                else:
                    S1.append('S')
        else:
            if S1[i] == 'S':
                if S1[i-1] == 'S':
                    S1.append('W')
                else:
                    S1.append('S')
            else:
                if S1[i-1] == 'S':
                    S1.append('S')
                else:
                    S1.append('W')
    if S1[-1] != a:
        continue
    S1 = S1[:N]
    if a == 'S' and b == 'S':
        if S[0] == 'o':
            if S1[-1] == 'S':
                print(''.join(S1))
                exit()
        else:
            if S1[-1] == 'W':
                print(''.join(S1))
                exit()
    elif a == 'S' and b == 'W':
        if S[0] == 'o':
            if S1[-1] == 'W':
                print(''.join(S1))
                exit()
        else:
            if S1[-1] == 'S':
                print(''.join(S1))
                exit()
    elif a == 'W' and b == 'S':
        if S[0] == 'o':
            if S1[-1] == 'W':
                print(''.join(S1))
                exit()
        else:
            if S1[-1] == 'S':
                print(''.join(S1))
                exit()
    else:
        if S[0] == 'o':
            if S1[-1] == 'S':
                print(''.join(S1))
                exit()
        else:
            if S1[-1] == 'W':
                print(''.join(S1))
                exit()
print(-1)

Submission status: Accepted

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

# 1 S -1 W
d = [0]*N

def check(a, b):
    d[-1] = a
    d[0] = b
    for i in range(N-2):
        if S[i] == "o":
            if d[i] == 1:
                d[i+1] = d[i-1]
            else:
                d[i+1] = d[i-1]*-1
        else:
            if d[i] == 1:
                d[i+1] = d[i-1]*-1
            else:
                d[i+1] = d[i-1]
        
    for i in range(N-1):
        if d[i] == 1:
            if S[i] == "o":
                if d[i-1] != d[i+1]:
                    return False
            else:
                if d[i-1] == d[i+1]:
                    return False
        else:
            if S[i] == "o":
                if d[i-1] == d[i+1]:
                    return False
            else:
                if d[i-1] != d[i+1]:
                    return False
    if d[N-1] == 1:
        if S[N-1] == "o":
            if d[N-2] != d[0]:
                return False
        else:
            if d[N-2] == d[0]:
                return False
    else:
        if S[N-1] == "o":
            if d[N-2] == d[0]:
                return False
        else:
            if d[N-2] != d[0]:
                return False
    return True

if check(1, 1):
    pass
elif check(1, -1):
    pass
elif check(-1, -1):
    pass
elif check(-1, 1):
    pass
else:
    print(-1)
    exit()

ans = ""
for i in range(N):
    if d[i] == 1:
        ans += "S"
    else:
        ans += "W"
print(ans)

Submission status: Accepted

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

def sheep(a,b):
    l=[0]*(n+1)
    l[0]=a
    l[1]=b
    m=[]
    for i in range(1,n):
        if s[i]=="o":
            if l[i]==0:
                l[i+1]=l[i-1]
            else:
                l[i+1]=(l[i-1]+1)%2
        else:
            if l[i]==0:
                l[i+1]=(l[i-1]+1)%2
            else:
                l[i+1]=l[i-1]
    x=0
    if s[0]=="o":
        if l[0]==0:
            x=l[1]
        else:
            x=(l[1]+1)%2
    else:
        if l[0]==0:
            x=(l[1]+1)%2
        else:
            x=l[1]
    if l[n]==l[0] and x==l[n-1]:
        for i in range(n):
            if l[i]==0:
                m.append("S")
            else:
                m.append("W")
        print("".join(m))
        exit()

sheep(0,0)
sheep(0,1)
sheep(1,0)
sheep(1,1)
print("-1")

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
s = input()

out = None
for a0, a1 in (("W", "S"), ("S", "W"), ("S","S"), ("W", "W")):
    ans = [None]*n
    ans[0] = a0
    ans[-1] = a1
    for i in range(n-1):
        v = int(s[i]=="o") + int(ans[i-1]=="S") + int(ans[i]=="S")
        if v%2==1:
            ans[i+1] = "S"
        else:
            ans[i+1] = "W"
    v = int(s[n-1]=="o") + int(ans[n-2]=="S") + int(ans[0]=="S") + int(ans[n-1]=="S")
    if ans[-1]==a1 and v%2==0:
        out = ans
if out is not None:
    write("".join(out))
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline
input = sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

#import numpy as np
from itertools import combinations

def main():
	n=II()
	s=input().decode()


	def check(a,b,c):
		A=[None]*(n+1)
		A[0]=a
		A[1]=b
		A[n-1]=c
		A[n]=a

		for i in range(1,n):
			if (s[i]=="o" and A[i]=="S") or (s[i]=="x" and A[i]=="W"):
				if A[i+1]==None:
					A[i+1]=A[i-1]
				else:
					if A[i+1]!=A[i-1]:
						return
			#if (s[i]=="o" and A[i]=="W") or (s[i]=="x" and A[i]=="S"):
			else:
				if A[i+1]==None:
					if A[i-1]=="S":
						A[i+1]="W"
					else:
						A[i+1]="S"
				else:
					if A[i+1]==A[i-1]:
						return

		print(*A[:-1],sep="")
		exit(0)

	if s[0]=="o":
		check("S","S","S")
		check("S","W","W")
		check("W","W","S")
		check("W","S","W")

	else:
		check("S","S","W")
		check("S","W","S")
		check("W","S","S")
		check("W","W","W")

	print(-1)













if __name__ == "__main__":
	main()