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 = list(input())

def judge() :
    # 最初の2個を決めれば良い
    for comb in (('S', 'S'), ('S', 'W'), ('W', 'S'), ('W', 'W')) :
        t = [None] * N
        t[0], t[1] = comb
            
        for i in range(1, N - 1) :
            if (s[i] == 'o') == (t[i] == 'S') :
                t[i + 1] = t[i - 1]
            else :
                t[i + 1] = 'S' if t[i - 1] == 'W' else 'W' 
        
        con1 = ((s[0] == 'o') == (t[0] == 'S')) == (t[N-1] == t[1])
        con2 = ((s[N - 1] == 'o') == (t[N - 1] == 'S')) == (t[N-2] == t[0])
        if con1 and con2 :
            return ''.join(t)
        
    return -1

print(judge())

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, s: str):
    def is_valid(v, prev, cur, nex):
        if (v == 'o' and nex == (prev + cur) % 2 or
            v == 'x' and nex == (prev + cur + 1) % 2):
            return True
        return False

    r = None
    for c0 in [0, 1]:
        for c1 in [0, 1]:
            ret = [0] * N
            ret[0] = c0
            ret[1] = c1
            for i in range(1, N - 1):
                if s[i] == 'o':
                    ret[i + 1] = (ret[i - 1] + ret[i]) % 2
                else:
                    ret[i + 1] = (ret[i - 1] + ret[i] + 1) % 2
            if (is_valid(s[N - 1], ret[N - 2], ret[N - 1], ret[0]) and 
                is_valid(s[0], ret[N - 1], ret[0], ret[1])):
                r = ['W' if t else 'S' for t in ret]
                #print(c0, c1, r)
                break
    if r:
        print(''.join(r))
    else:
        print(-1)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    s = next(tokens)  # type: str
    solve(N, s)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

o = "o"
for a in [0, 1]:
  for b in [0, 1]:
    L = ["" for _ in range(N)]
    L[0] = a
    L[1] = b
    for i in range(1, N - 1):
      if s[i] == o:
        if L[i] == 0:
          L[i + 1] = L[i - 1]
        else:
          L[i + 1] = 1 - L[i - 1]
      else:
        if L[i] == 0:
          L[i + 1] = 1 - L[i - 1]
        else:
          L[i + 1] = L[i - 1]
    if s[-1] == o:
      if L[-1] == 0:
        if L[-2] != L[0]:
          continue
      else:
        if L[-2] == L[0]:
          continue
    else:
      if L[-1] == 0:
        if L[-2] == L[0]:
          continue
      else:
        if L[-2] != L[0]:
          continue
    if s[0] == o:
      if L[0] == 0:
        if L[1] != L[-1]:
          continue
      else:
        if L[1] == L[-1]:
          continue
    else:
      if L[0] == 0:
        if L[1] == L[-1]:
          continue
      else:
        if L[1] != L[-1]:
          continue
    t = ""
    for i in range(N):
      if L[i] == 0:
        t += "S"
      else:
        t += "W"
    print(t)
    exit()

print(-1)

Submission status: Accepted

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

def construct(a0, a1):
    a = [None] * N # True: sheep, False: wolf
    a[0] = a0
    a[1] = a1
    for i in range(1, N - 1):
        if a[i]:
            if s[i] == 'o':
                a[i + 1] = a[i - 1]
            elif s[i] == 'x':
                a[i + 1] = not a[i - 1]
        else:
            if s[i] == 'o':
                a[i + 1] = not a[i - 1]
            elif s[i] == 'x':
                a[i + 1] = a[i - 1]
    for i in [0, N - 1]:
        if a[i]:
            if s[i] == 'o' and a[(i + 1) % N] != a[(i - 1) % N]:
                return None
            elif s[i] == 'x' and a[(i + 1) % N] == a[(i - 1) % N]:
                return None
        else:
            if s[i] == 'o' and a[(i + 1) % N] == a[(i - 1) % N]:
                return None
            elif s[i] == 'x' and a[(i + 1) % N] != a[(i - 1) % N]:
                return None
    return a

def solve():
    for a0 in [False, True]:
        for a1 in [False, True]:
            a = construct(a0, a1)
            if a is not None:
                return "".join(map(lambda x: 'S' if x else 'W', a))
    return "-1"

print(solve())

Submission status: Accepted

Solution code:
n = int(input())
s = [c == 'o' for c in input()]
def next_s(s, flag):
  d = {'S' : 'W', 'W' : 'S'}
  if flag:
    return s
  else:
    return d[s]

def sim(s0):
  ans = ['.' for _ in range(n+1)]
  ans[0] = s0[0]
  ans[1] = s0[1]
  for i in range(2, n+1):
    if ans[i-1] == 'S':
      ans[i] = next_s(ans[i-2], s[i-1])
    else:
      ans[i] = next_s(ans[i-2], not s[i-1])
  res = ans[1] == ans[-2]
  if s0[0] == 'S':
    if res == s[0] and ans[-1] == ans[0]:
      return ans[:-1]
  else:
    if res != s[0] and ans[-1] == ans[0]:
      return ans[:-1]
  return False

def solve():
  for item in ["SS", "SW", "WS", "WW"]:
    ans = sim(item)
    if ans:
      return print(''.join(ans))
  return print(-1)

solve()

Submission status: Accepted

Solution code:
n = int(input())
s = input()
s = s + s[0]

inv = { "S": "W", "W": "S" }

for zero, one in [["S", "S"], ["S", "W"], ["W", "S"], ["W", "W"]]:
    animals = [zero, one]
    for i in range(2, n + 2):
        if animals[i - 1] == "S":
            if s[i - 1] == "o":
                animals.append(animals[i - 2])
            else:
                animals.append(inv[animals[i - 2]])
        else:
            if s[i - 1] == "o":
                animals.append(inv[animals[i - 2]])
            else:
                animals.append(animals[i - 2])
    if animals[0] == animals[n] and animals[1] == animals[n + 1]:
        print("".join(animals[0:n]))
        exit(0)

print(-1)

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

N = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()


def flip(c):
    return 'W' if c == 'S' else 'S'


def solve(a1, a2):
    """
    :param a1:
    :param a2:
    :rtype: str
    """
    ans = a1 + a2
    cursor = 1
    while cursor < N:
        if S[cursor] == 'o' and ans[-1] == 'S' or S[cursor] == 'x' and ans[-1] == 'W':
            ans += ans[-2]
        else:
            ans += flip(ans[-2])
        cursor += 1

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


# 最初の 2 個が決まれば最後まで決まる
for a1, a2 in itertools.product('SW', repeat=2):
    ret = solve(a1, a2)
    if ret:
        print(ret)
        exit()
print(-1)

Submission status: Accepted

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

d = {'S':'W','W':'S'}

def make(s1,s2):
    a = [s1,s2]
    for i in range(N):
        s1,s2 = a[-2:]
        if s2 == 'S':
            if s[i] == 'o':
                s0 = s1
            else:
                s0 = d[s1]
        else:
            if s[i] == 'o':
                s0 = d[s1]
            else:
                s0 = s1
        a.append(s0)
    return a

for s1 in ['S','W']:
    for s2 in ['S','W']:
        a = make(s1,s2)
        possible = a[:2]==a[-2:]
        if possible:
            break
    if possible:
        break

if possible:
    print(''.join(a[1:N+1]))
else:
    print(-1)

Submission status: Accepted

Solution code:
N = int(input())
S = input().replace('o', '0').replace('x', '1')
S = list(map(int, S))

for pattern in [[0, 0], [0, 1], [1, 0], [1, 1]]:
    for s in S[1:]:
        if pattern[-2] ^ pattern[-1] ^ s == 0:
            pattern.append(0)
        else:
            pattern.append(1)

    pattern = pattern[:-1]
    for i, s in enumerate(S):
        if pattern[i - 1] ^ pattern[(i + 1) % N] ^ s != pattern[i]:
            break
    else:
        pattern = ''.join(map(str, pattern)).replace('0', 'S').replace('1', 'W')
        print(*pattern, sep='')
        break
else:
    print(-1)

Submission status: Accepted

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

def sheep_wolf_allocator(given_string ,first_allocate, second_allocate):
    '''
    与えられた文字列を満たすように1...Nまで羊/狼を割り当てる。
    最後にN匹目と1匹目の検証を行う。
    
    引数
    ------------------------------
    given_string: 動物の主張 ooxoxox..
    first_allocate: 1番に割り当てる動物(S/W)
    second_allocate: 2番に割り当てる動物(S/W)
    
    戻り値
    ------------------------------
    検証失敗時 -> -1
    swallocation: 羊/狼の割当結果文字列, 検証失敗時は返さない
    '''
    
    def verse(ws_char):
        if ws_char == "W":
            return "S"
        else:
            return "W"
        
    
    # allocation
    swallocation = []
    swallocation.append(first_allocate)
    swallocation.append(second_allocate)
    
    N = len(given_string)
    
    for pi in range(1, N):
        if swallocation[pi] == 'S':
            if given_string[pi] == 'o':
                swallocation.append(swallocation[pi - 1])
            else:
                swallocation.append(verse(swallocation[pi - 1]))
        else:
            if given_string[pi] == 'o':
                swallocation.append(verse(swallocation[pi - 1]))
            else:
                swallocation.append(swallocation[pi - 1])
    
    # verification
    if swallocation[0] == 'S':
        if given_string[0] == 'o':
            if swallocation[N - 1] != swallocation[1]:
                return -1
        else:
            if swallocation[N - 1] == swallocation[1]:
                return -1
    else:
        if given_string[0] == 'o':
            if swallocation[N - 1] == swallocation[1]:
                return -1
        else:
            if swallocation[N - 1] != swallocation[1]:
                return -1
    
    if swallocation[0] != swallocation[N]:
        return -1
    
    return ''.join(swallocation[:N])
  
def main():
    judge1 = sheep_wolf_allocator(s, "S", "S")
    judge2 = sheep_wolf_allocator(s ,"S", "W")
    judge3 = sheep_wolf_allocator(s ,"W", "S")
    judge4 = sheep_wolf_allocator(s ,"W", "W")
    
    if judge1 != -1:
        print(judge1)
        return
    
    if judge2 != -1:
        print(judge2)
        return
    
    if judge3 != -1:
        print(judge3)
        return
    
    if judge4 != -1:
        print(judge4)
        return
    
    print(-1)
    return
  
main()

Submission status: Accepted

Solution code:
N=int(input())
s=input()
for T in ["SS","SW","WS","WW"]:
    for i in range(1,N-1):
        if T[-1]=="S":
            if s[i]=="o":
                T+=T[-2]
            else:
                if T[-2]=="S":
                    T+="W"
                else:
                    T+="S"
        else:
            if s[i]=="x":
                T+=T[-2]
            else:
                if T[-2]=="S":
                    T+="W"
                else:
                    T+="S"
    F=True
    if s[i+1]=="o":
        if T[-1]=="S" and T[-2]==T[0]:
            F=False
        elif T[-1]=="W" and T[-2]!=T[0]:
            F=False
    else:
        if T[-1]=="S" and T[-2]!=T[0]:
            F=False
        elif T[-1]=="W" and T[-2]==T[0]:
            F=False
    if F:
        continue
    F=True
    if s[0]=="o":
        if T[0]=="S" and T[-1]==T[1]:
            F=False
        elif T[0]=="W" and T[-1]!=T[1]:
            F=False
    else:
        if T[0]=="S" and T[-1]!=T[1]:
            F=False
        elif T[0]=="W" and T[-1]==T[1]:
            F=False
    if F:
        continue
    print(T)
    quit()
print(-1)

Submission status: Accepted

Solution code:
def check(prev_, now_, S, N):
    rev = {'S':'W', 'W':'S'}
    prev, now = prev_, now_
    p  = [now]
    for i in range(1,N+1):
        if S[i] == 'o':
            if now == 'S':
                prev, now = now, prev
            else:
                prev, now = now, rev[prev]
        else:
            if now == 'S':
                prev, now = now, rev[prev]
            else:
                prev, now = now, prev
        p.append(now)
    if prev_ == prev and now_ == now:
        print(''.join(p[:-1]))
    return prev_ == prev and now_ == now

N=int(input())
S=input()
S = S[-1]+S+S[0]

ptn = ['SS', 'SW', 'WS', 'WW']
for sw in ptn:
    if check(sw[0], sw[1], S, N):
        break
else:
    print(-1)

Submission status: Accepted

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


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


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

Submission status: Accepted

Solution code:
n=int(input())
s=input()
ans=0
for j in range(2):
    for k in range(2):
        ans1=""
        last=j+1 #狼1 羊2
        start=k+1
        a0=last
        a1=start
        for i in range(n):
            if a1==1:
                ans1+="W"
            else:
                ans1+="S"

            if [a0,a1]==[1,1] and s[i]=='o':
                a0=a1
                a1=2
            elif [a0,a1]==[1,1] and s[i]=='x':
                a0=a1
                a1=1
            elif [a0,a1]==[1,2] and s[i]=='o':
                a0=a1
                a1=1
            elif [a0,a1]==[1,2] and s[i]=='x':
                a0=a1
                a1=2
            elif [a0,a1]==[2,1] and s[i]=='o':
                a0=a1
                a1=1
            elif [a0,a1]==[2,1] and s[i]=='x':
                a0=a1
                a1=2
            elif [a0,a1]==[2,2] and s[i]=='o':
                a0=a1
                a1=2
            elif [a0,a1]==[2,2] and s[i]=='x':
                a0=a1
                a1=1

        if a0==last and a1==start:
            ans=1
            break
    if ans==1:
        break
if ans==1:
    print(ans1)

else:
    print(-1)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
ANS=-1
def check(s,a,b,c):
    if s=="o":
        if b=="S" and a==c:
            return True
        elif b=="W" and a!=c:
            return True
    else:
        if b=="S" and a!=c:
            return True
        elif b=="W" and a==c:
            return True
    return False
for start in ["SS","SW","WS","WW"]:
    ans=start
    for i in range(2,N):
        if S[i-1]=="o":
            if ans[i-2]==ans[i-1]:
                ans+="S"
            else:
                ans+="W"
        else:
            if ans[i-2]==ans[i-1]:
                ans+="W"
            else:
                ans+="S"
    if check(S[0],ans[N-1],ans[0],ans[1]) and check(S[N-1],ans[N-2],ans[N-1],ans[0]):
        ANS=ans
        break
print(ANS)

Submission status: Accepted

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

## 0:sheep, 1:wolf
first_state_circle = [[0,0,0],[0,1,1],[1,0,1],[1,1,0]] ## [1st,2nd,-1th]
first_state_cross = [[0,0,1],[0,1,0],[1,0,0],[1,1,1]] ## [1st,2nd,-1th]
transtable = str.maketrans({'0':'S', '1':'W'})

if S[0] == 'o':
  first_state = first_state_circle
else:
  first_state = first_state_cross

for state in first_state:
  lst = [-1]*N
  lst[0] = state[0]
  lst[1] = state[1]
  for i in range(1,N-1):
    lst[i+1] = (lst[i-1] + lst[i] + (S[i]=='x')) % 2
  #print(state,lst)
  if lst[N-1] != state[2]:
    continue
  if lst[0] != (lst[N-2] + lst[N-1] + (S[N-1]=='x')) % 2:
    continue
  ans = ''.join(map(str,lst)).translate(transtable)
  print(ans)
  exit()
else:
  print('-1')

Submission status: Accepted

Solution code:
n = int(input())
s = input()
l = ['SS','SW','WS','WW']

for i in range(n):
  for j in range(len(l)):
    l[j] += 'SW'[::-1 if s[i]=='o' else 1][l[j][i]==l[j][i+1]]
for i in range(len(l)):
  if l[i][0]==l[i][n] and l[i][1]==l[i][n+1]:
    print(l[i][1:n+1])
    exit()
print(-1)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
l = ['SS','WS','SW','WW']

for i in range(n):
  for j in range(len(l)):
    l[j] += 'SW'[::-1 if s[i]=='o' else 1][l[j][i]==l[j][i+1]]
for i in range(len(l)):
  if l[i][1]==l[i][n+1] and l[i][0]==l[i][n]:
    print(l[i][1:n+1])
    exit()
print(-1)

Submission status: Accepted

Solution code:
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def neg(i):
    if i == 'S':
        return 'W'
    else:
        return 'S'

s  = ''
n = 0

def check(build):
    poss = [0, n-1]
    for pos in poss:
        if build[pos] == 'S':
            if s[pos] == 'o' and build[(pos-1+n)%n] != build[(pos+1+n)%n]:
                return False
            if s[pos] == 'x' and build[(pos-1+n)%n] == build[(pos+1+n)%n]:
                return False
        else:
            if s[pos] == 'o' and build[(pos-1+n)%n] == build[(pos+1+n)%n]:
                return False
            if s[pos] == 'x' and build[(pos-1+n)%n] != build[(pos+1+n)%n]:
                return False
    
    return True

def solve():
    global s, n
    n = f()[0]
    s = input()

    for i in [ 'S', 'W']:
        for j in ['S','W']:
            build = i + j
            
            for k in range(1, n-1):
                if s[k] == 'o':
                    if build[k] == 'S':
                        build += build[k-1]
                    else:
                        build += neg(build[k-1])
                else:
                    if build[k] == 'S':
                        build += neg(build[k-1])
                    else:
                        build += build[k-1]

            if check(build):
                print(build)
                return

    print(-1)


solve()

Submission status: Accepted

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

# 最初の2人を決めると全部決まっていく

def make_arr(first,second):
  result = [first,second]
  last,prev = second,first
  for ox in s[1:] + s[0]:
    if (ox == 'o') ^ (last == 0):
      # 両隣が異なる
      last,prev = 1-prev,last
    else:
      # 両隣が一致
      last,prev = prev,last
    result.append(last)
    continue
  bl = (result[0] == result[-2]) and (result[1] == result[-1])
  return bl,result[:-2]


answer = '-1'
for fi,se in [[0,0],[0,1],[1,0],[1,1]]:
  bl,li = make_arr(fi,se)
  if bl:
    answer = ''.join(['W' if x else 'S' for x in li])
print(answer)

Submission status: Accepted

Solution code:
n = int(input())
s = [1 if si == 'o' else 0 for si in list(input())]
t0 = [[1, 1], [1, 0], [0, 1], [0, 0]]
for ti in t0:
    flag = True
    for i in range(1, n - 1):
        if ti[i] * (1 - s[i]) or (1 - ti[i]) * s[i]:
            ti.append(1 - ti[i - 1])
        else:
            ti.append(ti[i - 1])
    for i in range(2):
        if ti[i - 1]:
            if (s[i - 1] and not ti[i - 2] == ti[i]) or (1 - s[i - 1] and ti[i - 2] == ti[i]):
                flag = False
        else:
            if (s[i - 1] and ti[i - 2] == ti[i]) or (1 - s[i - 1] and not ti[i - 2] == ti[i]):
                flag = False
    if flag:
        ans = ['S' if x else 'W' for x in ti]
        print(''.join(ans))
        exit()
print(-1)

Submission status: Accepted

Solution code:
d ={"o":0, "x":1}
e =["S","W"]
n = int(input())
s = [d[t] for t in input()]

for i in range(4):
  a = [-1]*(n+2)
  a[0] = i%2
  a[1] = i//2
  for i in range(n):
    a[i+2] = a[i] ^ a[i+1] ^ s[i]
  if a[0] == a[n] and a[1] == a[n+1]:
    print("".join([e[t] for t in a[1:n+1]]))
    quit()
print(-1)

Submission status: Accepted

Solution code:
d ={"o":0, "x":1}
e =["S","W"]
n = int(input())
s = [d[t] for t in input()]
#print(s)

u = [0,1,0,1]
v = [0,0,1,1]

for i in range(4):
  a = [-1]*(n+2)
  a[0] = u[i]
  a[1] = v[i]
  for i in range(n):
    a[i+2] = a[i] ^ a[i+1] ^ s[i]
  if a[0] == a[n] and a[1] == a[n+1]:
    print("".join([e[t] for t in a[1:n+1]]))
    quit()
print(-1)

Submission status: Accepted

Solution code:
N=int(input())
s=[c=="x" for c in input()]
ans = [0]*N
end = False
for c0 in (0,1):
    ans[0] = c0
    for cN in (0,1):
        ans[-1] = cN
        for i,c in enumerate(s[:-2]):
            ans[i+1] = ans[i-1] ^ (ans[i]^c)
        end = (ans[-1]==ans[-3]^(ans[-2]^s[-2])) and (ans[0]==ans[-2]^(ans[-1]^s[-1]))
        if end:break
    if end:break
if end:print("".join(["SW"[a] for a in ans]))
else:print(-1)

Submission status: Accepted

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

ans = ['SS', 'SW', 'WS', 'WW']
s += s[0]
for i in range(4):
    for j in range(1, N+1):
        if ans[i][j] == 'S':
            if s[j] == 'o':
                ans[i] += ans[i][j-1]
            else:
                if ans[i][j-1] == 'S':
                    ans[i] += 'W'
                else:
                    ans[i] += 'S'
        else:
            if s[j] == 'x':
                ans[i] += ans[i][j-1]
            else:
                if ans[i][j-1] == 'S':
                    ans[i] += 'W'
                else:
                    ans[i] += 'S'

    if ans[i][0] == ans[i][-2] and ans[i][1] == ans[i][-1]:
        print(ans[i][:-2])
        exit()

print(-1)

Submission status: Accepted

Solution code:
N = int(input())
S = list(map(int, input().replace('o', '0').replace('x', '1')))

for p in [[0, 0], [0, 1], [1, 0], [1, 1]]:
    for s in S[1:]:
        if p[-1] ^ p[-2] ^ s == 1:
            p.append(1)
        else:
            p.append(0)

    if (p[0] == p[-1]) and (p[-2] ^ p[-3] ^ p[0] ^ S[-1] == 0) and (p[0] ^ p[-2] ^ p[1] ^ S[0] == 0):
        print(''.join(map(str, p[:-1])).replace('0', 'S').replace('1', 'W'))
        break
else:
    print(-1)

Submission status: Accepted

Solution code:
n = int(input())
s = [1 if si == 'o' else 0 for si in list(input())]
t0 = [[1, 1], [1, 0], [0, 1], [0, 0]]
for ti in t0:
    flag = True
    for i in range(1, n - 1):
        if ti[i] * (1 - s[i]) or (1 - ti[i]) * s[i]:
            ti.append(1 - ti[i - 1])
        else:
            ti.append(ti[i - 1])
    for i in range(2):
        if ti[i - 1]:
            if (s[i - 1] and not ti[i - 2] == ti[i]) or (1 - s[i - 1] and ti[i - 2] == ti[i]):
                flag = False
        else:
            if (s[i - 1] and ti[i - 2] == ti[i]) or (1 - s[i - 1] and not ti[i - 2] == ti[i]):
                flag = False
    if flag:
        ans = ['S' if x else 'W' for x in ti]
        print(''.join(ans))
        exit()
print(-1)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
if N == 3:
    if S == "ooo":
        print("SSS")
    elif S == "xxx":
        print("SSW")
    else:
        print(-1)
    exit()
def solve(first, second):
    R = [None] * N
    R[0] = first
    if (S[0] == "o" and R[0] == "S") or (S[0] == "x" and R[0] == "W"):
        R[1] = R[-1] = second
    else:
        R[1] = second
        R[-1] = "S" if second != "S" else "W"
    for i, s in enumerate(S):
        if i == 0:
            continue
        if (s == "o" and R[i] == "S") or (s == "x" and R[i] == "W"):
            new = R[i - 1]
        else:
            new = "W" if R[i - 1] != "W" else "S"
        if i == N - 2:
            if new != R[i + 1]:
                return False, None
        if i == N - 1:
            if new != R[0]:
                return False, None
            else:
                return True, R
        R[i + 1] = new
for f, s in [("S", "S"), ("S", "W"), ("W", "S"), ("W", "W")]:
    ok, result = solve(f, s)
    if ok:
        print("".join(result))
        break
else:
    print(-1)

Submission status: Accepted

Solution code:
#coding;:utf-8

N=input()
s=raw_input()

def f(i):
    return i%len(s)

def ok(buf):
    for i in range(len(buf)):
        if buf[i]:
            if s[i] == "o":
                if buf[f(i-1)] != buf[f(i+1)]: return False
            else:
                if buf[f(i-1)] == buf[f(i+1)]: return False
        else:
            if s[i] == "o":
                if buf[f(i-1)] == buf[f(i+1)]: return False
            else:
                if buf[f(i-1)] != buf[f(i+1)]: return False            
    return True

OK=[]
# True: sheep; False: wolf
for b in range(1<<3):
    buf=[None] * N
    if b&0b001:buf[0]=True
    else:buf[0]=False
    if (b&0b010)>>1:buf[1]=True
    else:buf[1]=False
    if (b&0b100)>>2:buf[-1]=True
    else:buf[-1]=False

    for i in range(2, N-1):
        if s[i-1] == "o":
            if buf[i-1]:
                buf[i]=buf[i-2]
            else:
                buf[i]=not buf[i-2]
        else:
            if buf[i-1]:
                buf[i]=not buf[i-2]
            else:
                buf[i]=buf[i-2]
    if ok(buf):
        OK.append("".join("S" if b else "W" for b in buf))
if len(OK)==0:
    print(-1)
else:
    print(OK[0])

Submission status: Accepted

Solution code:
import sys

def check(pos, S, index):
    N = len(S)
    right = (index + 1) % N
    left = (index + (N - 1)) % N

    if pos[index] == 0:
        if S[index] == 'o':
            return pos[left] == pos[right]
        else:
            return pos[left] != pos[right]
    else:
        if S[index] == 'o':
            return pos[left] != pos[right]
        else:
            return pos[left] == pos[right]


def make_pos(pos, S):
    """Sheep: 0, Wolf: 1"""
    N = len(S)
    for i in range(1, N-1):
        if pos[i] == 0:
            if S[i] == 'o':
                pos[i+1] = pos[i-1]
            else:
                pos[i+1] = (pos[i-1] + 1) % 2

        else:
            if S[i] == 'o':
                pos[i+1] = (pos[i-1] + 1) % 2
            else:
                pos[i+1] = pos[i-1]

    if check(pos, S, 0) and check(pos, S, N-1):
        return pos
    else:
        return False


def main():
    input = sys.stdin.readline
    N = int(input())
    S = str(input().strip())

    # Case 1: SSxxx
    pos = [-1 for _ in range(N)]
    pos[0] = 0
    pos[1] = 0
    pos = make_pos(pos, S)
    if pos:
        ans = ['S' if n == 0 else 'W' for n in pos]
        return ''.join(ans)

    # Case 2: SWxxx
    pos = [-1 for _ in range(N)]
    pos[0] = 0
    pos[1] = 1
    pos = make_pos(pos, S)
    if pos:
        ans = ['S' if n == 0 else 'W' for n in pos]
        return ''.join(ans)

    # Case 3: WSxxx
    pos = [-1 for _ in range(N)]
    pos[0] = 1
    pos[1] = 0
    pos = make_pos(pos, S)
    if pos:
        ans = ['S' if n == 0 else 'W' for n in pos]
        return ''.join(ans)

    # Case 4: WWxxx
    pos = [-1 for _ in range(N)]
    pos[0] = 1
    pos[1] = 1
    pos = make_pos(pos, S)
    if pos:
        ans = ['S' if n == 0 else 'W' for n in pos]
        return ''.join(ans)

    return -1


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
n=int(input())
a=input()
s="SW"
for d in range(2):
    for c in range(2):
        k=s[d]+s[c]
        for i in range(2,n+2):
            if k[i-1]=="S":
                if a[(i-1)%n]=="o":
                    k+=k[i-2]
                else:
                    k+=("W" if k[i-2]=="S" else "S")
            else:
                if a[(i-1)%n]=="o":
                    k+=("W" if k[i-2]=="S" else "S")
                else:
                    k+=k[i-2]
        else:
            if k[0]==k[-2] and k[1]==k[-1]:
                print(k[:-2])
                exit()
else:
    print(-1)

Submission status: Accepted

Solution code:
def menagerie(N: int, s: str) -> str:
    # Sheep: True, Wolf: False

    # 0 番目と 1 番目の道具ぶつの組み合わせだけ全探索。
    # その 2 頭が決まればあとは一意に決まる。
    is_sheeps = [[None] * N for _ in range(4)]

    # SS
    is_sheeps[0][:2] = True, True
    # SW
    is_sheeps[1][:2] = True, False
    # WS
    is_sheeps[2][:2] = False, True
    # WW
    is_sheeps[3][:2] = False, False

    for n in range(1, N):
        for is_sheep in is_sheeps:
            if (s[n] == 'o') == is_sheep[n]:
                # n 番目の動物が羊で発言が 'o'、あるいは
                # 狼で発言が 'x' なら n 番目の両隣は同じ動物
                is_sheep[(n + 1) % N] = is_sheep[n - 1]
            else:
                # n 番目の動物が羊で発言が 'x'、あるいは
                # 狼で発言が 'o' なら n 番目の両隣は違う動物
                is_sheep[(n + 1) % N] = not is_sheep[n - 1]

    for i, is_sheep in enumerate(is_sheeps):
        if is_sheep[0] != (i // 2 == 0):
            # n-1 番目の動物の発言を検証したときに、
            # 先頭の動物が仮定と矛盾する。
            continue
        if ((s[0] == 'o') == is_sheep[0]) != (is_sheep[1] == is_sheep[-1]):
            # 先頭の動物の発言を検証したときに、
            # 先頭の動物が仮定と矛盾している。
            continue
        return ''.join('S' if b else 'W' for b in is_sheep)

    return '-1'


if __name__ == "__main__":
    N = int(input())
    s = input()
    ans = menagerie(N, s)
    print(ans)