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:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


# ワーシャルフロイド (任意の2頂点の対に対して最短経路を求める)
# 計算量n^3 (nは頂点の数)
def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定



# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
n = int(input())
s = input()
impossible = True
for i in ["S", "W"]:
    for j in ["S", "W"]:
        x = i + j
        # print(x)
        for k in range(1, n - 1):
            if s[k] == "o" and x[-1] == "S":
                if x[-2] == "S":
                    x += "S"
                else:
                    x += "W"
            elif s[k] == "o" and x[-1] == "W":
                if x[-2] == "S":
                    x += "W"
                else:
                    x += "S"
            elif s[k] == "x" and x[-1] == "S":
                if x[-2] == "S":
                    x += "W"
                else:
                    x += "S"
            elif s[k] == "x" and x[-1] == "W":
                if x[-2] == "S":
                    x += "S"
                else:
                    x += "W"
            # if i == "S" and j == "S":
                # print(x, k)
        # print(x)
        ok = True
        if (s[-1] == "o" and x[-1] == "S") or (s[-1] == "x" and x[-1] == "W"):
            if x[-2] != x[0]:
                ok = False
        elif x[-2] == x[0]: 
            ok = False
        if (s[0] == "o" and x[0] == "S") or (s[0] == "x" and x[0] == "W"):
            if x[-1] != x[1]:
                ok = False
        elif x[-1] == x[1]:
            ok = False
        if ok and impossible:
            print(x)
            impossible = False
if impossible:
    print(-1)

Submission status: Accepted

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

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    def check_no_contradict(n, new_s, pattern):
        animals = [None] * (n + 2)
        animals[1], animals[2] = pattern
        animals[0] = animals[2] if (animals[1] and new_s[1] == 'o') or (not animals[1] and new_s[1] == 'x') else not animals[2]
        for i in range(2, n + 1):
            animals[i+1] = animals[i-1] if (animals[i] and new_s[i] == 'o') or (not animals[i] and new_s[i] == 'x') else not animals[i-1]
        if animals[0] == animals[n] and animals[1] == animals[n + 1]:
            return animals[1:n+1]
        else:
            return []


    
    n = ii()
    s = input()
    new_s = s[-1] + s + s[0]    # [1]...[n] が本来の証言たち
    for pattern in product([True, False], repeat=2):
        result = check_no_contradict(n, new_s, pattern)
        if result:
            print(''.join(list(map(lambda x: 'S' if x else 'W', result))))
            exit()
    print(-1)





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    s = input()
    L = ["S", "W"]

    for first in L:
        for second in L:
            res = ["" for _ in range(n)]
            res[0] = first
            res[1] = second
            for i in range(1, n - 1):
                if s[i] == "o":
                    if res[i] == "S" and res[i - 1] == "S":
                        res[i + 1] = "S"
                    elif res[i] == "S" and res[i - 1] == "W":
                        res[i + 1] = "W"
                    elif res[i] == "W" and res[i - 1] == "W":
                        res[i + 1] = "S"
                    else:
                        res[i + 1] = "W"
                else:
                    if res[i] == "S" and res[i - 1] == "S":
                        res[i + 1] = "W"
                    elif res[i] == "S" and res[i - 1] == "W":
                        res[i + 1] = "S"
                    elif res[i] == "W" and res[i - 1] == "W":
                        res[i + 1] = "W"
                    else:
                        res[i + 1] = "S"

            if s[-1] == "o":
                if (res[-1] == "S" and res[-2] != res[0]) or (res[-1] == "W" and res[-2] == res[0]):
                    continue
            else:
                if (res[-1] == "S" and res[-2] == res[0]) or (res[-1] == "W" and res[-2] != res[0]):
                    continue

            if s[0] == "o":
                if (res[0] == "S" and res[-1] != res[1]) or (res[0] == "W" and res[-1] == res[1]):
                    continue
            else:
                if (res[0] == "S" and res[-1] == res[1]) or (res[0] == "W" and res[-1] != res[1]):
                    continue

            print("".join(res))
            break
        else:
            continue
        break
    else:
        print(-1)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

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

def wolfsheep(xy):
    global n,s
    result=[xy[0],xy[1]]

    for i in range(1,n+1):
        s+=s[0]
        if result[i]=="S":
            if s[i]=="o":
                result.append(result[i-1])
            else:
                result.append(rev(result[i-1]))
        else:
            if s[i]=="o":
                result.append(rev(result[i-1]))
            else:
                result.append(result[i-1])

    if result[0]==result[n] and result[1]==result[n+1]:
        return result
    else:
        return 0

#SWパターン
tmp= wolfsheep("SW")
if tmp!=0:
    print("".join(tmp[:-2]))
    exit()

#SSパターン
tmp= wolfsheep("SS")
if tmp!=0:
    print("".join(tmp[:-2]))
    exit()
#WWパターン
tmp= wolfsheep("WW")
if tmp!=0:
    print("".join(tmp[:-2]))
    exit()
#WSパターン
tmp= wolfsheep("WS")
if tmp!=0:
    print("".join(tmp[:-2]))
    exit()

print(-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    s=input()
    s=s+s[0]
    for j in range(4):
        l=[-1]*(N+2)
        for k in range(2):
            l[k]=(j>>k)&1
        for i in range(1,N+1):
            if l[i]==0:
                if s[i-1]=='o':
                    l[i+1]=l[i-1]
                else:
                    l[i+1]=int(not l[i-1])
            else:
                if s[i-1]=='o':
                    l[i+1]=int(not l[i-1])
                else:
                    l[i+1]=l[i-1]
        if l[0]==l[-2] and l[1]==l[-1]:
            for x in l[1:N+1]:
                if x==0:
                    print('S',end='')
                else:
                    print('W',end='')
            print('')
            exit()
    print(-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def convert(s):
    if s == 'S' or s == 'o':
        return 1
    else:
        return -1


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

cands = [['S', 'S'], ['S', 'W'], ['W', 'S'], ['W', 'W']]

for cand in cands:
    for i in range(1, len(s)-1):
        if cand[-1] == 'S':
            if s[i] == 'o' and cand[-2] == 'S':
                cand.append('S')
            elif s[i] == 'x' and cand[-2] == 'S':
                cand.append('W')
            elif s[i] == 'o' and cand[-2] == 'W':
                cand.append('W')
            else:
                cand.append('S')
        else:
            if s[i] == 'o' and cand[-2] == 'S':
                cand.append('W')
            elif s[i] == 'x' and cand[-2] == 'S':
                cand.append('S')
            elif s[i] == 'o' and cand[-2] == 'W':
                cand.append('S')
            else:
                cand.append('W')
    if (convert(cand[0]) * convert(cand[-1]) * convert(cand[1]) * convert(s[0]) == 1) and \
            (convert(cand[0]) * convert(cand[-1]) * convert(cand[-2]) * convert(s[-1]) == 1):
        print(''.join(cand))
        exit()

print(-1)

Submission status: Accepted

Solution code:
N = int(input())

s = input()


def fnc(x1, x2):
    pre = x1  # s[-1] の仮定
    curr = x2  # s[0] の仮定
    ans = []
    for i in range(N):
        if curr == 1:  # 羊
            if s[i] == 'o':
                nv = pre
            else:
                nv = (pre + 1) % 2
        else:  # 狼
            if s[i] == 'x':
                nv = pre
            else:
                nv = (pre + 1) % 2
        pre = curr
        curr = nv
        ans.append(pre)

    if pre == x1 and curr == x2:
        return ans
    else:
        return None


def solve():
    for i in [1, 0]:
        for j in [1, 0]:
            ans = fnc(i, j)
            if ans:
                return ans
    return None


if __name__ == '__main__':
    ans = solve()
    if not ans:
        print(-1)
        exit()

    for a in ans:
        print('S' if a else 'W', end='')
    print()

Submission status: Accepted

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

def sw(sl,dp):
    for i in range(1,n-1):
        if sl[i]=="o" and dp[i]=="S":
            dp[i+1] =dp[i-1]
        elif sl[i] =="o" and dp[i]=="W":
            if dp[i-1] =="S":
                dp[i+1] = "W"
            else:
                dp[i+1] = "S"
        elif sl[i]=="x" and dp[i]=="S":
            if dp[i-1] =="S":
                dp[i+1] = "W"
            else:
                dp[i+1] = "S"
        else:
            dp[i+1] = dp[i-1]

sl = list(s)
dp =[0]*n
dp[0]="S"
dp[1]="S"
sw(sl,dp)
if sl[0] =="o":
    if dp[n-1] =="W":
        pass
    elif sl[n-1] =="x":
        if dp[n-2] =="S":
            pass
        else:
            res = ''.join(dp)
            print(res)
            exit()
    elif sl[n-1] =="o":
        if dp[n-2] =="S":
            res = ''.join(dp)
            print(res)
            exit()
        else:
            pass
else:
    if dp[n-1] =="S":
        pass
    elif sl[n-1] =="x":
        if dp[n-2] =="W":
            pass
        else:
            res = ''.join(dp)
            print(res)
            exit()
    elif sl[n-1] =="o":
        if dp[n-2] =="W":
            res = ''.join(dp)
            print(res)
            exit()
        else:
            pass

dp =[0]*n
dp[0]="S"
dp[1]="W"
sw(sl,dp)
if sl[0] =="o":
    if dp[n-1] =="S":
        pass
    elif sl[n-1] =="x":
        if dp[n-2] =="W":
            pass
        else:
            res = ''.join(dp)
            print(res)
            exit()
    elif sl[n-1] =="o":
        if dp[n-2] =="W":
            res = ''.join(dp)
            print(res)
            exit()
        else:
            pass
else:
    if dp[n-1] =="W":
        pass
    elif sl[n-1] =="x":
        if dp[n-2] =="S":
            pass
        else:
            res = ''.join(dp)
            print(res)
            exit()
    elif sl[n-1] =="o":
        if dp[n-2] =="S":
            res = ''.join(dp)
            print(res)
            exit()
        else:
            pass
    
dp =[0]*n
dp[0]="W"
dp[1]="S"
sw(sl,dp)
if sl[0] =="o":
    if dp[n-1] =="S":
        pass
    elif sl[n-1] =="x":
        if dp[n-2] =="S":
            pass
        else:
            res = ''.join(dp)
            print(res)
            exit()
    elif sl[n-1] =="o":
        if dp[n-2] =="S":
            res = ''.join(dp)
            print(res)
            exit()
        else:
            pass
else:
    if dp[n-1] =="W":
        pass
    elif sl[n-1] =="x":
        if dp[n-2] =="W":
            pass
        else:
            res = ''.join(dp)
            print(res)
            exit()
    elif sl[n-1] =="o":
        if dp[n-2] =="W":
            res = ''.join(dp)
            print(res)
            exit()
        else:
            pass
        
dp =[0]*n
dp[0]="W"
dp[1]="W"
sw(sl,dp)
if sl[0] =="o":
    if dp[n-1] =="W":
        pass
    elif sl[n-1] =="x":
        if dp[n-2] =="W":
            pass
        else:
            res = ''.join(dp)
            print(res)
            exit()
    elif sl[n-1] =="o":
        if dp[n-2] =="W":
            res = ''.join(dp)
            print(res)
            exit()
        else:
            pass
else:
    if dp[n-1] =="S":
        pass
    elif sl[n-1] =="x":
        if dp[n-2] =="S":
            pass
        else:
            res = ''.join(dp)
            print(res)
            exit()
    elif sl[n-1] =="o":
        if dp[n-2] =="S":
            res = ''.join(dp)
            print(res)
            exit()
        else:
            pass

print(-1)

Submission status: Accepted

Solution code:
import itertools
N=int(input())
slist=[x=="o" for x in input()]
#print(slist)

answer_list=[None]*N

ok=False
for p1,p2 in itertools.product([True,False],repeat=2):
  answer_list[0]=p1
  answer_list[1]=p2
  
  for i in range(2,N):
    if answer_list[i-1]==slist[i-1]:
      answer_list[i]=answer_list[i-2]
    else:
      answer_list[i]=not answer_list[i-2]
        
  contra=False
  for i in range(N):
    l=(i-1)%N
    r=(i+1)%N
    if (answer_list[i]==slist[i])^(answer_list[l]==answer_list[r]):
      contra=True
  if not contra:
    ok=True
    break
    
if ok:
  sw_list=[]
  for ans in answer_list:
    if ans:
      sw_list.append("S")
    else:
      sw_list.append("W")
  print("".join(sw_list))
else:
  print(-1)

Submission status: Accepted

Solution code:
N=int(input())
slist=[x=="o" for x in input()]
#print(slist)

answer_list=[0]*N

ok=False
for p1,p2 in [(1,1),(1,-1),(-1,1),(-1,-1)]:
  answer_list[0]=p1
  answer_list[1]=p2
  
  for i in range(2,N):
    if answer_list[i-1]==1:
      if slist[i-1]:
        answer_list[i]=answer_list[i-2]
      else:
        answer_list[i]=-answer_list[i-2]
    else:
      if slist[i-1]:
        answer_list[i]=-answer_list[i-2]
      else:
        answer_list[i]=answer_list[i-2]
        
  contra=False
  for i in range(N):
    l=(i-1)%N
    r=(i+1)%N
    if answer_list[i]==1:
      if slist[i]:
        if answer_list[l]!=answer_list[r]:
          contra=True
      else:
        if answer_list[l]==answer_list[r]:
          contra=True
    else:
      if slist[i]:
        if answer_list[l]==answer_list[r]:          
          contra=True
      else:
        if answer_list[l]!=answer_list[r]:
          contra=True

  if not contra:
    ok=True
    break
    
if ok:
  sw_list=[]
  for ans in answer_list:
    if ans==1:
      sw_list.append("S")
    else:
      sw_list.append("W")
  print("".join(sw_list))
else:
  print(-1)

Submission status: Accepted

Solution code:
import copy

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

flag = False
begin_list = [["S", "S"], ["W", "S"], ["S", "W"], ["W", "W"]]

for i in range(4):
  sub = copy.deepcopy(begin_list[i])
  judge = True
  for j in range(2, n):
    if s[j-1] == "o":
      if sub[j-1] == "S":
        if sub[j-2] == "S":
          sub.append("S")
        else:
          sub.append("W")
      else:
        if sub[j-2] == "S":
          sub.append("W")
        else:
          sub.append("S")
    else:
      if sub[j-1] == "S":
        if sub[j-2] == "S":
          sub.append("W")
        else:
          sub.append("S")
      else:
        if sub[j-2] == "S":
          sub.append("S")
        else:
          sub.append("W")
  if s[-1] == "o":
    if (sub[-1] == "S" and sub[-2] != sub[0]) or (sub[-1] == "W" and sub[-2] == sub[0]):
      continue
  else:
    if (sub[-1] == "S" and sub[-2] == sub[0]) or (sub[-1] == "W" and sub[-2] != sub[0]):
      continue
  if s[0] == "o":
    if (sub[0] == "S" and sub[-1] != sub[1]) or (sub[0] == "W" and sub[-1] == sub[1]):
      continue
  else:
    if (sub[0] == "S" and sub[-1] == sub[1]) or (sub[0] == "W" and sub[-1] != sub[1]):
      continue
  flag = True
  break

if flag:
  print("".join(sub))
else:
  print(-1)

Submission status: Accepted

Solution code:
def check(li,N):
    for i in range(N):
        if (s[i]=='o' and li[i]==0)or(s[i]=='x' and li[i]==1):
            if(li[(i+1)%N]!=-1 and li[(i+1)%N]!=li[i-1]):
                return False
            else:
                li[(i+1)%N]=li[i-1]
        elif (s[i]=='o' and li[i]==1)or(s[i]=='x' and li[i]==0):
            if(li[(i+1)%N]!=-1 and li[(i+1)%N]==li[i-1]):
                return False
            else:
                li[(i+1)%N]=int(not li[i-1])
    return True
    
def output(li):
    for i in range(N):
        if li[i]==1:
            print('W',end='')
        else:
            print('S',end='')
    print()

N=int(input())
s=input()
for i in range(2):
    for j in range(2):
        li=[-1]*N
        li[0]=i
        if(i==0 and s[0]=='o')or(i==1 and s[0]=='x'):
            li[-1]=j;li[1]=j
        elif(i==1 and s[0]=='o')or(i==0 and s[0]=='x'):
            li[-1]=j;li[1]=j^1
        if(check(li,N)):
            output(li)
            exit()
print(-1)

Submission status: Accepted

Solution code:
n,s=int(input()),input()
s+=s[:2]
# 羊:0 狼:1
for i in range(2):
    for j in range(2):
        a=[0]*(n+2)
        a[0]=i
        a[1]=j
        for k in range(1,n+1):
            if a[k]==0:
                if s[k]=="o":
                    a[k+1]=a[k-1]
                else:
                    a[k+1]=not a[k-1]
            else:
                if s[k]=="o":
                    a[k+1]=not a[k-1]
                else:
                    a[k+1]=a[k-1]
        if a[0]==a[n] and a[1]==a[n+1]:
            print(*["W" if k else "S" for k in a[:n]],sep="")
            exit()
print(-1)

Submission status: Accepted

Solution code:
import sys
import queue


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7


def main():
    N = int(input())
    s = input()
    Animal = ["WW", "WS", "SS", "SW"]
    for i in range(1, N - 1):
        if s[i] == "o":
            for j in range(4):
                if Animal[j][-1] == "S":
                    Animal[j] = Animal[j] + Animal[j][-2]
                else:
                    if Animal[j][-2] == "S":
                        Animal[j] = Animal[j] + "W"
                    else:
                        Animal[j] = Animal[j] + "S"
        else:
            for j in range(4):
                if Animal[j][-1] == "S":
                    if Animal[j][-2] == "S":
                        Animal[j] = Animal[j] + "W"
                    else:
                        Animal[j] = Animal[j] + "S"
                else:
                    Animal[j] = Animal[j] + Animal[j][-2]
    for i in range(4):
        animal = Animal[i]
        if s[-1] + s[0] == "xo":
            for a in ["WWWS", "WSSS", "SWSW", "SSWW"]:
                if animal[-2:] + animal[:2] == a:
                    print(animal)
                    return
            else:
                continue

        elif s[-1] + s[0] == "xx":
            for a in ["WWWW", "WSSW", "SWSS", "SSWS"]:
                if animal[-2:] + animal[:2] == a:
                    print(animal)
                    return
                else:
                    continue

        elif s[-1] + s[0] == "ox":
            for a in ["WWSS", "WSWS", "SSSW", "SWWW"]:
                if animal[-2:] + animal[:2] == a:
                    print(animal)
                    return
        elif s[-1] + s[0] == "oo":
            for a in ["WWSW", "WSWW", "SSSS", "SWWS"]:
                if animal[-2:] + animal[:2] == a:
                    print(animal)
                    return
                else:
                    continue
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    S = input()

    # 0番目と1番目を決めれば他が全部決まる
    for s0, s1 in [("S", "W"), ("W", "S"), ("S", "S"), ("W", "W")]:
        ans = [None] * N
        ans[0] = s0
        ans[1] = s1
        for i in range(1, N - 1):
            if ans[i] == "S":
                s = S[i]
            else:
                if S[i] == "o":
                    s = "x"
                else:
                    s = "o"

            if s == "o":
                ans[i + 1] = ans[i - 1]
            else:
                if ans[i - 1] == "S":
                    ans[i + 1] = "W"
                else:
                    ans[i + 1] = "S"

        if ans[-1] == "S":
            if S[-1] == "o":
                if ans[-2] == ans[0]:
                    pass
                else:
                    continue
            else:
                if ans[-2] != ans[0]:
                    pass
                else:
                    continue
        else:
            if S[-1] == "o":
                if ans[-2] != ans[0]:
                    pass
                else:
                    continue
            else:
                if ans[-2] == ans[0]:
                    pass
                else:
                    continue

        if ans[0] == "S":
            if S[0] == "o":
                if ans[-1] == ans[1]:
                    print(*ans, sep="")
                    return
                else:
                    continue
            else:
                if ans[-1] != ans[1]:
                    print(*ans, sep="")
                    return
                else:
                    continue
        else:
            if S[0] == "o":
                if ans[-1] != ans[1]:
                    print(*ans, sep="")
                    return
                else:
                    continue
            else:
                if ans[-1] == ans[1]:
                    print(*ans, sep="")
                    return
                else:
                    continue

    else:
        print(-1)


if __name__ == "__main__":
    main()