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:
#最初の2匹を割り当てることで解答文字列ansは一意に決まる。
#最初に[SW][WS][SS][WW]の4通りで決めウチすることで円環の接続点を見比べることができる
#脳死で4パターン同じ処理をコピペ。

N=int(input())
S=input()

def solve(n,s):

#[SW]の場合
  ans="SW"
  if s[0]=="o":
    ch="W"
  else:
    ch="S"
  for i in range(1,n):
    if (ans[-1]=="S" and s[i]=="o") or (ans[-1]=="W" and s[i]=="x") :
      ans = ans + ans[-2]
    elif ans[-1]=="S" and s[i]=="x" and ans[-2]=="S":
      ans = ans + "W"
    elif ans[-1]=="S" and s[i]=="x" and ans[-2]=="W":
      ans = ans + "S"
    elif ans[-1]=="W" and s[i]=="o" and ans[-2]=="S":
      ans = ans + "W"
    else:
      ans = ans + "S"
  if ans[-2]==ch and ans[-1]==ans[0]:
    return ans[:-1]

#[WS]の場合
  ans="WS"
  if s[0]=="o":
    ch="W"
  else:
    ch="S"
    
  for i in range(1,n):
    if (ans[-1]=="S" and s[i]=="o") or (ans[-1]=="W" and s[i]=="x") :
      ans = ans + ans[-2]
    elif ans[-1]=="S" and s[i]=="x" and ans[-2]=="S":
      ans = ans + "W"
    elif ans[-1]=="S" and s[i]=="x" and ans[-2]=="W":
      ans = ans + "S"
    elif ans[-1]=="W" and s[i]=="o" and ans[-2]=="S":
      ans = ans + "W"
    else:
      ans = ans + "S"
  if ans[-2]==ch and ans[-1]==ans[0]:
    return ans[:-1]
  
#[SS]の場合
  ans="SS"
  if s[0]=="o":
    ch="S"
  else:
    ch="W"
    
  for i in range(1,n):
    if (ans[-1]=="S" and s[i]=="o") or (ans[-1]=="W" and s[i]=="x") :
      ans = ans + ans[-2]
    elif ans[-1]=="S" and s[i]=="x" and ans[-2]=="S":
      ans = ans + "W"
    elif ans[-1]=="S" and s[i]=="x" and ans[-2]=="W":
      ans = ans + "S"
    elif ans[-1]=="W" and s[i]=="o" and ans[-2]=="S":
      ans = ans + "W"
    else:
      ans = ans + "S"
  if ans[-2]==ch and ans[-1]==ans[0]:
    return ans[:-1]
  
#[WW]の場合
  ans="WW"
  if s[0]=="o":
    ch="S"
  else:
    ch="W"
    
  for i in range(1,n):
    if (ans[-1]=="S" and s[i]=="o") or (ans[-1]=="W" and s[i]=="x") :
      ans = ans + ans[-2]
    elif ans[-1]=="S" and s[i]=="x" and ans[-2]=="S":
      ans = ans + "W"
    elif ans[-1]=="S" and s[i]=="x" and ans[-2]=="W":
      ans = ans + "S"
    elif ans[-1]=="W" and s[i]=="o" and ans[-2]=="S":
      ans = ans + "W"
    else:
      ans = ans + "S"
  if ans[-2]==ch and ans[-1]==ans[0]:
    return ans[:-1]
  
  return -1

print(solve(N,S))

Submission status: Accepted

Solution code:
#a = int(input())
#b,c = map(int,input().split())
#s = input()
#list_s = list(input())
#list_int = list(map(int,input().split()))

#list = [0 for i in range(n)]
#dp = [[0 for i in range(A)] for j in range(B)]

#list_int 並べて出力 print (' '.join(map(str,ans_li)))
#list_str 並べて出力 print (' '.join(list))

# 2進数 format(10, 'b') # '1010'

# aa=[int(input()) for i in range(n)]

#for i,name in enumerate(list)

''' 二次元配列を一列ずつ
for i in ans:
	print(*i)
'''
''' heapq
queue = []
heapq.heapify(queue) #heapqの作成
heapq.heappush(queue,num) #numのpush(値の追加)
pop = heapq.heappop(queue) #numのpop(最小値の出力)
pop = heapq.heappushpop(queue,num) #push -> pop

'''

from collections import defaultdict
import sys,heapq,bisect,math,itertools,string
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7


N = int(input())
s = input()
s = s + s[0]

def check(SW):
	global N
	global s
	for i in range(1,N+1):
		if SW[i]:
			if s[i] == 'o':
				SW.append(SW[i-1])
			else:
				SW.append(not SW[i-1])
		else:
			if s[i] == 'o':
				SW.append(not SW[i-1])
			else:
				SW.append(SW[i-1])

	if SW[N] == SW[0] and SW[N+1] == SW[1]:
		for i in range(N):
			if SW[i]:
				sys.stdout.write("S")
			else:
				sys.stdout.write("W")
		print()
		sys.exit()

check([True,True])
check([True,False])
check([False,True])
check([False,False])
print(-1)

Submission status: Accepted

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

a=[0]*n

for i in range(n):
    if s[i]=="o":
        a[i]=1
    else:
        a[i]=-1

ans=[0]*n

flag=-1
S=["0"]*n

ans[0]=1
ans[1]=1

for i in range(2,n):
    ans[i]=a[i-1]*ans[i-1]*ans[i-2]
else:
    c1=a[0]*ans[0]*ans[n-1]
    c2=a[n-1]*ans[n-1]*ans[n-2]
    if c1==ans[1] and c2==ans[0]:
        flag=1
        for i in range(n):
            if ans[i]==1:
                S[i]="S"
            else:
                S[i]="W"
        print(''.join(S))

if flag<0:

    ans[0]=-1
    ans[1]=1

    for i in range(2,n):
        ans[i]=a[i-1]*ans[i-1]*ans[i-2]
    else:
        c1=a[0]*ans[0]*ans[n-1]
        c2=a[n-1]*ans[n-1]*ans[n-2]
        if c1==ans[1] and c2==ans[0]:
            flag=1
            for i in range(n):
                if ans[i]==1:
                    S[i]="S"
                else:
                    S[i]="W"
            print(''.join(S))

if flag<0:

    ans[0]=1
    ans[1]=-1

    for i in range(2,n):
        ans[i]=a[i-1]*ans[i-1]*ans[i-2]
    else:
        c1=a[0]*ans[0]*ans[n-1]
        c2=a[n-1]*ans[n-1]*ans[n-2]
        if c1==ans[1] and c2==ans[0]:
            flag=1
            for i in range(n):
                if ans[i]==1:
                    S[i]="S"
                else:
                    S[i]="W"
            print(''.join(S))

if flag<0:

    ans[0]=-1
    ans[1]=-1

    for i in range(2,n):
        ans[i]=a[i-1]*ans[i-1]*ans[i-2]
    else:
        c1=a[0]*ans[0]*ans[n-1]
        c2=a[n-1]*ans[n-1]*ans[n-2]
        if c1==ans[1] and c2==ans[0]:
            flag=1
            for i in range(n):
                if ans[i]==1:
                    S[i]="S"
                else:
                    S[i]="W"
            print(''.join(S))

if flag<0:
    print(flag)

Submission status: Accepted

Solution code:
from itertools import product

N = int(input())
S = input()


def r(x):
    if x == 'S':
        return 'W'
    else:
        return 'S'


def f(x1, x2, s):
    if s == 'o':
        if x1 == 'S':
            return x2
        else:
            return r(x2)
    else:
        if x1 == 'S':
            return r(x2)
        else:
            return x2


ans = ['-1']
for x1, x2 in product('SW', repeat=2):
    res = [x1, x2]
    for i in range(N):
        x1, x2 = x2, f(x1, x2, S[i])
        res.append(x2)
    if res[:2] == res[-2:]:
        ans = res[1:-1]
        break
print(''.join(ans))

Submission status: Accepted

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

def rev(anim):
    if anim == 'S':
        return 'W'
    else:
        return 'S'

def check(comb, ans):
    if comb[1] == 'S':
        if ans == 'o':
            return comb[0] == comb[2]
        else:
            return comb[0] != comb[2]
    else:
        if ans == 'o':
            return comb[0] != comb[2]
        else:
            return comb[0] == comb[2]

import sys
for T in ('SS', 'SW', 'WS', 'WW'):
    for i in range(2, n):
        ans = S[i-1]
        anim = T[i-1]
        prev = T[i-2]
        if ans == 'o':
            if anim == 'S':
                T += prev
            else:
                T += rev(prev)
        else:
            if anim == 'S':
                T += rev(prev)
            else:
                T += prev
    comb1 = T[n-2]+T[n-1]+T[0]
    ans1 = S[n-1]
    comb2 = T[n-1]+T[0]+T[1]
    ans2 = S[0]
    if check(comb1, ans1) and check(comb2, ans2):
        print(T)
        sys.exit(0)
print(-1)

Submission status: Accepted

Solution code:
N = int(input())
s = input()
animals = ['SS', 'SW', 'WS', 'WW']
for i, animal in enumerate(animals):
  for j in range(N):
    a = 1 if animals[i][-1] == 'S' else -1
    b = 1 if animals[i][-2] == 'S' else -1
    c = 1 if s[(j + 1) % N] == 'o' else -1
    animals[i] += 'S' if a * b * c > 0 else 'W'
ans = -1
for animal in animals:
  if animal[:2] == animal[-2:]:
    ans = animal[:N]
print(ans)

Submission status: Accepted

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

def next(p, c, s):
    if p == 'S' and c == 'S':
        return 'S' if s == 'o' else 'W'
    elif p == 'S' and c == 'W':
        return 'W' if s == 'o' else 'S'
    elif p == 'W' and c == 'S':
        return 'W' if s == 'o' else 'S'
    elif p == 'W' and c == 'W':
        return 'S' if s == 'o' else 'W'
    else:
        return None

flag = False
for p, c in [('S', 'S'), ('S', 'W'), ('W', 'S'), ('W', 'W')]:
    r = p + c
    for i in range(1, N-1):
        r += next(r[-2], r[-1], s[i])

    if next(r[-2], r[-1], s[N-1]) == r[0] and next(r[-1], r[0], s[0]) == r[1]:
        flag = True
        print(r)
        break

if not flag:
    print(-1)

Submission status: Accepted

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

m = {
  'S': {
    'S': {'o': 'S', 'x': 'W'},
    'W': {'o': 'W', 'x': 'S'},
  },
  'W': {
    'S': {'o': 'W', 'x': 'S'},
    'W': {'o': 'S', 'x': 'W'},
  }
}
import itertools
for p, c in itertools.product(['S','W'], ['S','W']):
  ans = [p, c]
  for a in s:
    p,c = c, m[p][c][a]
    ans.append(c)
  if ans[:2] == ans[-2:]:
    print(''.join(ans[1:-1]))
    exit(0)
print(-1)

Submission status: Accepted

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

def search_pattern(input_list):
    temp = copy.deepcopy(input_list)
    for i in range(2, n):
        if temp[i - 1] == 'S':
            if s[i - 1] == 'o':
                temp.append(temp[i - 2])
            else:
                if temp[i - 2] == 'S':
                    temp.append('W')
                else:
                    temp.append('S')
        else:
            if s[i - 1] == 'x':
                temp.append(temp[i - 2])
            else:
                if temp[i - 2] == 'S':
                    temp.append('W')
                else:
                    temp.append('S')

    if temp[n - 1] == 'S':
        if s[n - 1] == 'o':
            if temp[n - 2] != temp[0]:
                return -1
        else:
            if temp[n - 2] == 'S':
                if temp[0] == 'S':
                    return -1
            else:
                if temp[0] != 'S':
                    return -1
    else:
        if s[n - 1] == 'x':
            if temp[n - 2] != temp[0]:
                return -1
        else:
            if temp[n - 2] == 'S':
                if temp[0] == 'S':
                    return -1
            else:
                if temp[0] != 'S':
                    return -1

    if temp[0] == 'S':
        if s[0] == 'o':
            if temp[n - 1] != temp[1]:
                return -1
        else:
            if temp[n - 1] == 'S':
                if temp[1] == 'S':
                    return -1
            else:
                if temp[1] != 'S':
                    return -1
    else:
        if s[0] == 'x':
            if temp[n - 1] != temp[1]:
                return -1
        else:
            if temp[n - 1] == 'S':
                if temp[1] == 'S':
                    return -1
            else:
                if temp[1] != 'S':
                    return -1
    print("".join(temp))
    exit()

search_pattern(list("SS"))
search_pattern(list("SW"))
search_pattern(list("WS"))
search_pattern(list("WW"))

print("-1")

Submission status: Accepted

Solution code:
import sys
N = int(input())
s = input()
r = ['SS', 'SW', 'WS', 'WW']
flag = [False, False]
for _i in range(4):
    for _j in range(1, N-1):
        if (s[_j] == 'o' and r[_i][_j] == 'S') or (s[_j] == 'x' and r[_i][_j] == 'W'):
            r[_i] += r[_i][_j-1]
        else:
            if r[_i][_j] == 'W':
                if r[_i][_j-1] == 'S':
                    r[_i] += 'W'
                else:
                    r[_i] += 'S'
            if r[_i][_j] == 'S':
                if r[_i][_j-1] == 'W':
                    r[_i] += 'S'
                else:
                    r[_i] += 'W'
    if (s[N-1] == 'o' and r[_i][N-1] == 'S') or (s[N-1] == 'x' and r[_i][N-1] == 'W'):
        if r[_i][N-2] == r[_i][0]:
            flag[0] = True
    else:
        if r[_i][N-2] != r[_i][0]:
            flag[0] = True
    if flag[0]:
            if (s[0] == 'o' and r[_i][0] == 'S') or (s[0] == 'x' and r[_i][0] == 'W'):
                if r[_i][N-1] == r[_i][1]:
                    flag[1] = True
            else:
                if r[_i][N-1] != r[_i][1]:
                    flag[1] = True
    if flag[0] and flag[1]:
        print(r[_i])
        break
    else:
        flag = [False, False]
if not(flag[0]) and not(flag[1]):
    print(-1)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
for p in ("SS", "SW", "WS", "WW"):  # N-1と0
    ans = p[1]
    ip = p
    for i in range(N):
        if S[i] == "o":
            if p[0] == p[1]:
                p = p[1] + "S"
            else:
                p = p[1] + "W"
        else:
            if p[0] == p[1]:
                p = p[1] + "W"
            else:
                p = p[1] + "S"
        ans += p[-1]
    if ans[-2:] == ip:
        print(ans[:-1])
        exit()
print(-1)

Submission status: Accepted

Solution code:
N=int(input())
s=input()
animals = ["" for _ in range(N)]

def convert(animal):
    if animal == "S":
        return "W"
    else:
        return "S"

def animalOnRight(left,center,sig):
    if center == "S":
        if sig == "o":
            return left
        else:
            return convert(left)
    else:
        if sig == "o":
            return convert(left)
        else:
            return left
for (a0,a1) in [("W","S"),("W","W"),("S","S"),("S","W")]:
    animals[0],animals[1] = (a0,a1)
    for i in range(N-2):
        animals[i+2] = animalOnRight(animals[i],animals[i+1],s[i+1])
        #print(animals)
    satisfied = (animalOnRight(animals[N-2],animals[N-1],s[N-1]) == animals[0]) and (animalOnRight(animals[N-1],animals[0],s[0]) == animals[1])
    if satisfied:
        for char in animals:
            print(char, end='')
        print()
        exit()
print(-1)

Submission status: Accepted

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

B = {"S":"W", "W":"S"}
def check(a0, a1):
    b0,b1 = a0,a1
    A = a1
    for i in range(N):
        if a1 == "S":
            if S[i] == "o":
                a2 = a0
            else:
                a2 = B[a0]
        else:
            if S[i] == "o":
                a2 = B[a0]
            else:
                a2 = a0
        A += a2
        a0,a1 = a1,a2
    if A[0] == A[N] and A[0] == b1 and A[N-1] == b0:
        return A[0:N]
    else:
        return -1

Ans = []
Ans.append(check("S","S"))
Ans.append(check("S","W"))
Ans.append(check("W","S"))
Ans.append(check("W","W"))

for ans in Ans:
    if ans == -1:
        continue
    else:
        print(ans)
        exit()
else:
    print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

N = int(input())
s = list(input())

def decide_i_plus_one(p, c, res):
  if c == 'S':
    if res == 'o':
      return p
    else:
      if p == 'S': return 'W'
      else:        return 'S'
  else:
    if res == 'o':
      if p == 'S': return 'W'
      else:        return 'S'
    else:
      return p

def valid(animals):
  # -2, -1, 0 のバリデーション
  if decide_i_plus_one(animals[-2], animals[-1], s[-1]) != animals[0]:
    return 0
  # -1, 0, 1 のバリデーション
  if decide_i_plus_one(animals[1], animals[0], s[0]) != animals[-1]:
    return 0

  # 0, 1, 2 のバリデーションは必要なし
  return 1

possible_pairs = [('S','S'), ('S','W'), ('W','S'), ('W','W')]
for (fst,snd) in possible_pairs:
  animals = []
  animals.append(fst)
  animals.append(snd)

  pi,ci = 0,1

  while 1:
    if ci == N-1:
      if valid(animals):
        print("".join(animals))
        exit(0)
      else:
        break

    n = decide_i_plus_one(animals[pi], animals[ci], s[ci])

    animals.append(n)
    pi += 1
    ci += 1

print("-1")

Submission status: Accepted

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

def makeans(ans):
        for c in s:
                if (ans[-1] == "S") ^ (c == "o") ^ (ans[-2] == "W"):
                        ans += "W"
                else:
                        ans += "S"

        return ans

for initial in ["SS","SW","WS","WW"]:
        ans = makeans(initial)
        if ans[0] == ans[-2] and ans[1] == ans[-1]:
                print(ans[1:-1])
                exit()

print("-1")

Submission status: Accepted

Solution code:
from itertools import product
N = int(input())
S = input()

C = product("SW", repeat=2)


for c in C:
    ans = list(c)
    for i in range(1, len(S)):
        # 羊
        if ans[-1] == "S":
            # 羊で〇なら同じ
            if S[i] == "o":
                ans.append(ans[-2])
            else:
                # 羊で×ならじゃないほう
                if ans[-2] == "S":
                    ans.append("W")
                else:
                    ans.append("S")
        # 狼
        else:
            # 狼で×なら同じ
            if S[i] == "x":
                ans.append(ans[-2])
            # 狼で〇ならじゃないほう
            else:
                if ans[-2] == "S":
                    ans.append("W")
                else:
                    ans.append("S")

    ans = ans[:-1]
    for i in range(N):
        if ans[i] == "S" and S[i] == "o":
            if ans[i-1] != ans[(i+1) % N]:
                break
        if ans[i] == "S" and S[i] == "x":
            if ans[i-1] == ans[(i+1) % N]:
                break
        if ans[i] == "W" and S[i] == "x":
            if ans[i-1] != ans[(i+1) % N]:
                break
        if ans[i] == "W" and S[i] == "o":
            if ans[i-1] == ans[(i+1) % N]:
                break
    else:
        print("".join(ans))
        break

else:
    print(-1)

Submission status: Accepted

Solution code:
def check(listx,s):
	num = (listx[-2]+listx[1])%2
	if num!=listx[0] and s[0]=="o": return True
	elif num==listx[0] and s[0]=="x": return True
	else: return False
n = int(input())
s = input()
x,flag,ans = [[1,1],[1,0],[0,1],[0,0]],False,""
for i in range(4):
	for j in range(1,n):
		if (s[j]=="o" and x[i][-1]==1) or (s[j]=="x" and x[i][-1]==0): x[i].append(x[i][-2])
		else: x[i].append(1-x[i][-2])
	if x[i][0]==x[i][-1] and check(x[i],s):
		flag = True
		break
if flag:
	for k in x[i][:n]:
		if k==1: ans+="S"
		else: ans+="W"
	print(ans)
else: print(-1)

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
t = [0] * n
# 0=sheep, 1=wolf

def check(one, two):
    t[0: 2] = [one, two]
    for i in range(n - 2):
        if (s[i + 1] == "o" and t[i + 1] == 0) or (s[i + 1] == "x" and t[i + 1] == 1):
            t[i + 2] = t[i]
        else:
            t[i + 2] = 1 - t[i]
    # print(t)
    a = ((s[-1] == "o" and t[-1] == 0) or (s[-1] == "x" and t[-1] == 1)) and t[-2] == t[0]
    b = ((s[-1] == "o" and t[-1] == 1) or (s[-1] == "x" and t[-1] == 0)) and t[-2] != t[0]
    c = ((s[0] == "o" and t[0] == 0) or (s[0] == "x" and t[0] == 1)) and t[-1] == t[1]
    d = ((s[0] == "o" and t[0] == 1) or (s[0] == "x" and t[0] == 0)) and t[-1] != t[1]
    if (a or b) and (c or d):
        return t
    else:
        return None
    
def sw(t):
    ans = []
    for i in range(n):
        if t[i] == 0:
            ans.append("S")
        else:
            ans.append("W")
    return("".join(ans))

# print(check(0, 0))
# print(check(0, 1))
# print(check(1, 0))
# print(check(1, 1))
if check(0, 0) is not None:
    print(sw(check(0, 0)))
elif check(0, 1) is not None:
    print(sw(check(0, 1)))
elif check(1, 0) is not None:
    print(sw(check(1, 0)))
elif check(1, 1) is not None:
    print(sw(check(1, 1)))
else:
    print(-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

N = int(input())
statements = list(str(input()))
patterns = [['S', 'S'], ['S', 'W'], ['W', 'S'], ['W', 'W']]
null_flg = 1

for pattern in patterns:
    animals = pattern
    for index in range(1, N-1):
        rule = statements[index] + animals[index]
        if rule == 'oS':
            animals.append(animals[index - 1])
        elif rule == 'xS':
            if animals[index - 1] == 'S':
                animals.append('W')
            else:
                animals.append('S')
        elif rule == 'oW':
            if animals[index - 1] == 'S':
                animals.append('W')
            else:
                animals.append('S')
        elif rule == 'xW':
            animals.append(animals[index - 1])

    last_flg = first_flg = 0
    last = statements[-1] + animals[-1]
    if last == 'oS':
        if animals[0] == animals[-2]:
            last_flg = 1
    elif last == 'xS':
        if animals[0] != animals[-2]:
            last_flg = 1
    elif last == 'oW':
        if animals[0] != animals[-2]:
            last_flg = 1
    elif last == 'xW':
        if animals[0] == animals[-2]:
            last_flg = 1

    if last_flg:
        first = statements[0] + animals[0]
        if first == 'oS':
            if animals[-1] == animals[1]:
                print(''.join(animals))
                null_flg = 0
                break
        elif first == 'xS':
            if animals[-1] != animals[1]:
                print(''.join(animals))
                null_flg = 0
                break
        elif first == 'oW':
            if animals[-1] != animals[1]:
                print(''.join(animals))
                null_flg = 0
                break
        elif first == 'xW':
            if animals[-1] == animals[1]:
                print(''.join(animals))
                null_flg = 0
                break

if null_flg:
    print('-1')

Submission status: Accepted

Solution code:
def d_menagerie(N, S):
    s = S + S[0:2]  # 円環状に並んでいることを考慮
    for ans in ['SS', 'SW', 'WS', 'WW']:  # Sは羊、Wは狼。1番と2番の種類を仮定する
        for i in range(1, N + 1):
            if (ans[-1] == 'S' and s[i] == 'o') or (ans[-1] == 'W' and s[i] == 'x'):
                # この場合、今注目している動物の両隣は同じ種類。
                # よって、今注目している動物の右隣を左隣と同じにする。
                ans += ans[-2]
            else:
                # 両隣は違う種類。右隣を左隣と逆にする。
                ans += ('S' if ans[-2] == 'W' else 'W')
        if ans[:2] == ans[N:]:
            # sの最初の2文字(仮定)と最後の2文字が一致した文字列のみ受理する。
            # 1つ見つければ良いので、すぐにbreakする
            ans = ans[:N]
            break
    else:  # どの割り当て方も矛盾した
        ans = '-1'
    return ans

N = int(input())
S = input().strip()
print(d_menagerie(N, S))

Submission status: Accepted

Solution code:
N = int(input())
ori1 = [0 for x in  range(N)]
fini = 0
s = input()

init = [[1,1],[1,-1],[-1,1],[-1,-1]]


for it in init:
    flag = 0
    ori = ori1.copy()
    ori[0] = it[0]
    ori[1] = it[1]
    for i in range(N):
        if i == 0:
            continue
        if ori[i] == 1:
            if s[i] == "o":
                if i == N-1:
                    if ori[0] != ori[i-1]:
                        flag = 1

                else:
                    ori[i+1] = ori[i-1]
            else:
                if i == N-1:
                    if ori[0] != -ori[i-1]:
                        flag = 1
                else:
                    ori[i+1] = -ori[i-1]
        else:
            if s[i] == "x":
                if i == N-1:
                    if ori[0] != ori[i-1]:
                        flag = 1
                else:
                    ori[i+1] = ori[i-1]
            else:
                if i == N-1:
                    if ori[0] != -ori[i-1]:
                        flag = 1
                else:
                    ori[i+1] = -ori[i-1]
    if ori[0] == 1:
        if s[0] == "o":
            if ori[1] != ori[-1]:
                flag = 1
        else:
            if ori[1] == ori[-1]:
                flag = 1
    else:
        if s[0] == "x":
            if ori[1] != ori[-1]:
                flag = 1
        else:
            if ori[1] == ori[-1]:
                flag = 1

    if flag == 0:
        ori = ["S" if x == 1 else "W" for x in ori]
        out = ""
        for o in ori:
            out += o
        print(out)
        fini = 1
        break
    else:
        continue

if fini == 0:
    print(-1)

Submission status: Accepted

Solution code:
n =int(input())
s = input()
cir = ['']*n
judge = ''
def convertSW(x):
  if x == 'S':
    return 'W'
  elif x == 'W':
    return 'S'
for i in range(4):
  if i == 0:
    cir[0],cir[1] = 'S','S'
  elif i == 1:
    cir[0],cir[1] = 'S','W'
  elif i == 2:
    cir[0],cir[1] = 'W','W'
  else:
    cir[0],cir[1] = 'W','S'
  if (s[0] == 'o' and cir[0] == 'S') or (s[0] == 'x' and cir[0] == 'W'):
    judge = cir[1]
  else:
    judge = convertSW(cir[1])
  for j in range(2,n):
    if (s[j-1] == 'o' and cir[j-1] == 'S') or (s[j-1] == 'x' and cir[j-1] == 'W'):
      cir[j] = cir[j-2]
    else:
      cir[j] = convertSW(cir[j-2])
  if (s[-1] == 'o' and cir[-1] == 'S') or (s[-1] == 'x' and cir[-1] == 'W'):
    if (cir[0] == cir[-2]) and (judge == cir[-1]):
      print(''.join(cir))
      exit()
  else:
    if cir[0] == convertSW(cir[-2]) and (judge == cir[-1]):
      print(''.join(cir))
      exit()
print(-1)

Submission status: Accepted

Solution code:
import sys

N=int(input())
S=input()

flgT=["SSS","SWW","WWS","WSW"]
flgF=["SSW","WSS","SWS","WWW"]

if S[0]=='o':
  for i in range(4):
    str=flgT[i]
    for j in range(1,N):
      if (S[j]=="o" and str[-1]=="S") or (S[j]=="x" and str[-1]=="W"):
        str=str+str[-2]
      else:
        if str[-2]=="W":
          str=str+"S"
        else:
          str=str+"W"
    if str[-2]==str[0] and str[-1]==str[1]:
      str=str[1:-1]
      print(str)
      sys.exit()
else:
  for i in range(4):
    str=flgF[i]
    for j in range(1,N):
      if (S[j]=="o" and str[-1]=="S") or (S[j]=="x" and str[-1]=="W"):
        str=str+str[-2]
      else:
        if str[-2]=="W":
          str=str+"S"
        else:
          str=str+"W"
    if str[-2]==str[0] and str[-1]==str[1]:
      str=str[1:-1]
      print(str)
      sys.exit()

print(-1)

Submission status: Accepted

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

def judge(a,b):
	t=[]
	t.append(a)
	t.append(b)

	for ind, i in enumerate(s):
		if ind==0:
			continue

		if i=="o" and t[ind]=="S":
			t.append(t[ind-1])
		elif i=="o" and t[ind]=="W":
			if t[ind-1]=="S":
				t.append("W")
			elif t[ind-1]=="W":
				t.append("S")
		elif i=="x" and t[ind]=="S":
			if t[ind-1]=="S":
				t.append("W")
			elif t[ind-1]=="W":
				t.append("S")
		elif i=="x" and t[ind]=="W":
			t.append(t[ind-1])

	if t[0]==t[-1]:
		if s[0]=="o" and t[0]=="S":
			if t[1]==t[-2]:
				print "".join(t[:-1])
				quit()
		elif s[0]=="o" and t[0]=="W":
			if t[1]!=t[-2]:
				print "".join(t[:-1])
				quit()
		elif s[0]=="x" and t[0]=="S":
			if t[1]!=t[-2]:
				print "".join(t[:-1])
				quit()
		elif s[0]=="w" and t[0]=="W":
			if t[1]==t[-2]:
				print "".join(t[:-1])
				quit()			
	else:
		return False

judge("S","S")
judge("S","W")
judge("W","S")
judge("W","W")
print -1

Submission status: Accepted

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

pat1 = [-1] * N
pat2 = [-1] * N
pat3 = [-1] * N
pat4 = [-1] * N

pat1[1] = pat2[1] = 1
pat3[1] = pat4[1] = 0

if s[1] == 'o':
	pat1[0] = pat1[2] = 0
	pat2[0] = pat2[2] = 1
	pat3[0] = pat4[2] = 0
	pat3[2] = pat4[0] = 1

else:
	pat1[0] = pat2[2] = 0
	pat2[0] = pat1[2] = 1
	pat3[0] = pat3[2] = 0
	pat4[2] = pat4[0] = 1


#print([pat1,pat2,pat3,pat4])

for i in range(2,N-1):
	for lis in [pat1,pat2,pat3,pat4]:
		if lis[i] == 1:
			if s[i] == 'o':
				lis[i+1] = lis[i-1]

			else:
				lis[i+1] = (lis[i-1] + 1)%2
		else:
			if s[i] == 'x':
				lis[i+1] = lis[i-1]

			else:
				lis[i+1] = (lis[i-1] + 1)%2

#print([pat1,pat2,pat3,pat4])

def ok1(List):
	global s
	if List[N-1] == 1:
		if s[N-1] == 'o':
			return List[N-2] == List[0]
		else:
			return List[N-2] != List[0]

	else:
		if s[N-1] == 'x':
			return List[N-2] == List[0]
		else:
			return List[N-2] != List[0]

def ok2(List):
	global s
	if List[0] == 1:
		if s[0] == 'o':
			return List[N-1] == List[1]
		else:
			return List[N-1] != List[1]

	else:
		if s[0] == 'x':
			return List[N-1] == List[1]
		else:
			return List[N-1] != List[1]





flg = []
for lis in [pat1,pat2,pat3,pat4]:
	if ok1(lis) and ok2(lis):
		flg = lis
		break
	
#print(flg)
ans = ""
if flg != []:
	for num in flg:
		if num ==  0:
			ans += 'W'
		else:
			ans += 'S'

	print(ans)

else:
	print(-1)

Submission status: Accepted

Solution code:
def d_Menagerie(N, S):
    s = S + S[0:2]  # 円環状に並んでいることを考慮
    for ans in ['SS', 'SW', 'WS', 'WW']:  # Sは羊、Wは狼。1番と2番の種類を仮定する
        cond = False
        for i in range(1, N + 1):
            if (ans[-1] == 'S' and s[i] == 'o') or (ans[-1] == 'W' and s[i] == 'x'):
                # この場合、今注目している動物の両隣は同じ種類。
                # よって、今注目している動物の右隣を左隣と同じにする。
                ans += ans[-2]
            else:
                # 両隣は違う種類。右隣を左隣と逆にする。
                ans += ('S' if ans[-2] == 'W' else 'W')
        if ans[:2] == ans[N:]:
            # sの最初の2文字(仮定)と最後の2文字が一致した文字列のみ受理する。
            # 1つ見つければ良いので、すぐにbreakする
            cond = True
            ans = ans[:N]
            break
    # 目的の文字列が存在すればその文字列を返し、存在しなければ-1を返す
    if cond:
        return ans
    else:
        return '-1'
    return None

N = int(input())
S = input().strip()
print(d_Menagerie(N, S))