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:
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) and ((s[0] == 'o') == is_sheep[0]) == (is_sheep[1] == is_sheep[-1]):
            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)

Submission status: Accepted

Solution code:
def is_ok(idx):
    flg = False
    bf = (idx - 1) % N
    af = (idx + 1) % N

    if t[idx] == 'S':
        if s[idx] == 'o':
            if t[af] == t[bf]:
                flg = True
        else:
            if t[af] != t[bf]:
                flg = True
    else:
        if s[idx] == 'x':
            if t[af] == t[bf]:
                flg = True
        else:
            if t[af] != t[bf]:
                flg = True
    return flg


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

ans = ['-1']
flg = False
for first in 'SW':
    for second in 'SW':
        t = [None for _ in range(N)]
        t[0] = first
        t[1] = second
        for i, ss in enumerate(s):
            if i <= 1: continue

            if t[i - 1] == 'S':
                if s[i - 1] == 'o':
                    t[i] = t[i - 2]
                else:
                    t[i] = 'W' if t[i - 2] == 'S' else 'S'
            else:
                if s[i - 1] == 'o':
                    t[i] = 'W' if t[i - 2] == 'S' else 'S'
                else:
                    t[i] = t[i - 2]
            # i番目の動物の種別を決める
        # print(t)

        if is_ok(0) and is_ok(N - 1):
            flg = True
            ans = t
            break

    if flg: break

print(''.join(ans))

Submission status: Accepted

Solution code:
n=int(input())
s=list(input())
s.append(s[0])
f=0
l=['S','S']
for j in range(4):
  for i in range(1,n+1):
    if l[i]=='S':
      if l[i-1]=='S':
        if s[i]=='o':
          l.append('S')
        else:
          l.append('W')
      else:
        if s[i]=='o':
          l.append('W')
        else:
          l.append('S')
    else:
      if l[i-1]=='S':
        if s[i]=='o':
          l.append('W')
        else:
          l.append('S')
      else:
        if s[i]=='o':
          l.append('S')
        else:
          l.append('W')
  if l[n+1]==l[1] and l[n]==l[0]:
    f=1
    break
  else:
    if j==0:
      l=['S','W']
    elif j==1:
      l=['W','S']
    elif j==2:
      l=['W','W']
    else:
      break
if f==0:
  print(-1)
else:
  l.pop()
  l.pop()
  print(''.join(l))

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 (s[i] =="o" and t[i]=="S") or (s[i]=="x" and t[i]=="W"):
            t += t[i-1]
        else:
            if t[i-1] =="S":
              t += "W"
            else:
              t +="S"
    if (t[N-2]==t[0] and ((s[N-1]=="o" and t[N-1]=="S") or (s[N-1]=="x" and t[N-1]=="W"))) or (t[N-2]!=t[0] and ((s[N-1]=="o" and t[N-1]=="W") or (s[N-1]=="x" and t[N-1]=="S"))):
         if (t[N-1]==t[1] and ((s[0]=="o" and t[0]=="S") or (s[0]=="x" and t[0]=="W"))) or (t[N-1]!=t[1] and ((s[0]=="o" and t[0]=="W") or (s[0]=="x" and t[0]=="S"))):
             print(t)
             break
else:
    print(-1)

Submission status: Accepted

Solution code:
def check(N, S, ans):
    for i in range(N):
        if (ans[i] == "S") ^ (S[i] == "o"):
            if ans[(i-1) % N] == ans[(i+1) % N]:
                return False
        else:
            if ans[(i-1) % N] != ans[(i+1) % N]:
                return False
    return True


def main():
    N = int(input())
    S = input()
    initials = ["SS", "SW", "WS", "WW"]
    for init in initials:
        ans = [""] * N
        ans[0] = init[0]
        ans[1] = init[1]
        for i in range(1, N-1):
            if (ans[i] == "S") ^ (S[i] == "o"):
                ans[i+1] = "W" if ans[i-1] == "S" else "S"
            else:
                ans[i+1] = ans[i-1]
        if check(N, S, ans):
            print("".join(ans))
            return
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N=int(input())
s=input()
flag=False
def check(s,bef,now,nex):
    if s=='o':
        if now=='S':
            if bef==nex:return True
        elif now=='W':
            if bef!=nex:return True
    elif s=='x':
        if now=='S':
            if bef!=nex:return True
        elif now=='W':
            if bef==nex:return True
    return False

for x in ['SS','SW','WS','WW']:
    if flag==True:break
    ans=x
    bef,now=x[0],x[1]
    for i in range(2,N):
        if s[i-1]=='o':
            if bef==now:
                ans+='S'
                bef,now=now,'S'
            elif bef!=now:
                ans+='W'
                bef,now=now,'W'
        elif s[i-1]=='x':
            if bef!=now:
                ans+='S'
                bef,now=now,'S'
            elif bef==now:
                ans+='W'
                bef,now=now,'W'
    if check(s[N-1],ans[N-2],ans[N-1],ans[0])==True and check(s[0],ans[N-1],ans[0],ans[1])==True:
        flag=True
        break
if flag==False:print('-1')
else:print(ans)

Submission status: Accepted

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

for fs in ["SS","SW","WW","WS"]:
    ANS=["A"]*N
    ANS[0],ANS[1]=fs[0],fs[1]
    for i in range(2,N):
        if ANS[i-1]=="S":
            if S[i-1]=="o":
                if ANS[i-2]=="S":
                    ANS[i]="S"

                else:
                    ANS[i]="W"

            else:
                if ANS[i-2]=="S":
                    ANS[i]="W"

                else:
                    ANS[i]="S"

        else:
            if S[i-1]=="o":
                if ANS[i-2]=="S":
                    ANS[i]="W"

                else:
                    ANS[i]="S"

            else:
                if ANS[i-2]=="S":
                    ANS[i]="S"

                else:
                    ANS[i]="W"

    if ANS[0]=="S":
        if S[0]=="o":
            if ANS[-1]!=ANS[1]:
                continue
        else:
            if ANS[-1]==ANS[1]:
                continue
    else:
        if S[0]=="o":
            if ANS[-1]==ANS[1]:
                continue
        else:
            if ANS[-1]!=ANS[1]:
                continue

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

    print("".join(ANS))
    break
else:
    print(-1)

Submission status: Accepted

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

def main():
	n = int(input())
	tmp = input()
	ans = list(tmp)
	
	ans_Q = []
	case = [["." for _ in range(n)] for _ in range(4)]
	case[0][0] = "S"
	case[0][1] = "S"
	case[1][0] = "W"
	case[1][1] = "W"
	case[2][0] = "S"
	case[2][1] = "W"
	case[3][0] = "W"
	case[3][1] = "S"
	
	for case_o in case:
		for i in range(1, n-1):
			if case_o[i] == "S" and ans[i] == "o":
				case_o[i+1] = case_o[i-1]
				continue
			if case_o[i] == "S" and ans[i] == "x":
				case_o[i+1] = run(case_o[i-1])
				continue
			if case_o[i] == "W" and ans[i] == "o":
				case_o[i+1] = run(case_o[i-1])
				continue
			if case_o[i] == "W" and ans[i] == "x":
				case_o[i+1] = case_o[i-1]
				continue
				
		if case_o[n-1] == "S" and ans[n-1] == "o":
			if case_o[0] == case_o[n-2]:
				if case_o[0] == "S" and ans[0] == "o":
					if case_o[1] == case_o[n-1]:
						ans_Q = case_o
						break
				if case_o[0] == "S" and ans[0] == "x":
					if case_o[1] != case_o[n-1]:
						ans_Q = case_o
						break
				if case_o[0] == "W" and ans[0] == "o":
					if case_o[1] != case_o[n-1]:
						ans_Q = case_o
						break
				if case_o[0] == "W" and ans[0] == "x":
					if case_o[1] == case_o[n-1]:
						ans_Q = case_o
						break
		if case_o[n-1] == "S" and ans[n-1] == "x":
			if case_o[0] != case_o[n-2]:
				if case_o[0] == "S" and ans[0] == "o":
					if case_o[1] == case_o[n-1]:
						ans_Q = case_o
						break
				if case_o[0] == "S" and ans[0] == "x":
					if case_o[1] != case_o[n-1]:
						ans_Q = case_o
						break
				if case_o[0] == "W" and ans[0] == "o":
					if case_o[1] != case_o[n-1]:
						ans_Q = case_o
						break
				if case_o[0] == "W" and ans[0] == "x":
					if case_o[1] == case_o[n-1]:
						ans_Q = case_o
						break
		if case_o[n-1] == "W" and ans[n-1] == "o":
			if case_o[0] != case_o[n-2]:
				if case_o[0] == "S" and ans[0] == "o":
					if case_o[1] == case_o[n-1]:
						ans_Q = case_o
						break
				if case_o[0] == "S" and ans[0] == "x":
					if case_o[1] != case_o[n-1]:
						ans_Q = case_o
						break
				if case_o[0] == "W" and ans[0] == "o":
					if case_o[1] != case_o[n-1]:
						ans_Q = case_o
						break
				if case_o[0] == "W" and ans[0] == "x":
					if case_o[1] == case_o[n-1]:
						ans_Q = case_o
						break
		if case_o[n-1] == "W" and ans[n-1] == "x":
			if case_o[0] == case_o[n-2]:
				if case_o[0] == "S" and ans[0] == "o":
					if case_o[1] == case_o[n-1]:
						ans_Q = case_o
						break
				if case_o[0] == "S" and ans[0] == "x":
					if case_o[1] != case_o[n-1]:
						ans_Q = case_o
						break
				if case_o[0] == "W" and ans[0] == "o":
					if case_o[1] != case_o[n-1]:
						ans_Q = case_o
						break
				if case_o[0] == "W" and ans[0] == "x":
					if case_o[1] == case_o[n-1]:
						ans_Q = case_o
						break
	
	if len(ans_Q) == 0:
		print(-1)
	else:
		word = ""
		for w in ans_Q:
			word = word + w
		print(word)
	
def run(cher):
	if cher == "W":
		return "S"
	else:
		return "W"
		
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
n,m = LI()
if m <= 2*n:print(m//2)
else:
    ans = n
    m -= 2*n
    ans += m//4
    print(ans)
"""

#D
def f(a,b,c):
    k = a^b
    if c == "x":
        k = 1-k
    return k
n = I()
s = S()
s.append(s[0])
na = ["S","W"]
pre = [0,0]
for i in range(1,n+1):
    pre.append(f(pre[-2],pre[-1],s[i]))
if pre[0] == pre[-2] and pre[1] == pre[-1]:
    for i in range(n-1):
        print(na[pre[i]],end = "")
    print(na[pre[n-1]])
    quit()
pre = [0,1]
for i in range(1,n+1):
    pre.append(f(pre[-2],pre[-1],s[i]))
if pre[0] == pre[-2] and pre[1] == pre[-1]:
    for i in range(n-1):
        print(na[pre[i]],end = "")
    print(na[pre[n-1]])
    quit()
pre = [1,0]
for i in range(1,n+1):
    pre.append(f(pre[-2],pre[-1],s[i]))
if pre[0] == pre[-2] and pre[1] == pre[-1]:
    for i in range(n-1):
        print(na[pre[i]],end = "")
    print(na[pre[n-1]])
    quit()
pre = [1,1]
for i in range(1,n+1):
    pre.append(f(pre[-2],pre[-1],s[i]))
if pre[0] == pre[-2] and pre[1] == pre[-1]:
    for i in range(n-1):
        print(na[pre[i]],end = "")
    print(na[pre[n-1]])
    quit()
print(-1)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
def solver(array):
    for index in range(1, n+1):
        if index == n:
            index = 0
        if array[index] == "S" and s[index]:
            if index == n - 1:
                if array[index-1] != array[0]:
                    return False
                else:
                    continue
            if index == 0:
                if array[-1] != array[1]:
                    return False
                else:
                    continue
            array[index + 1] = array[index - 1]
        elif array[index] == "S" and not s[index]:
            if index == n - 1:
                if array[index-1] == array[0]:
                    return False
                else:
                    continue
            if index == 0:
                if array[-1] == array[1]:
                    return False
                else:
                    continue
            if array[index - 1] == "W":
                array[index + 1] = "S"
            else:
                array[index + 1] = "W"
        elif array[index] == "W" and s[index]:
            if index == n - 1:
                if array[index-1] == array[0]:
                    return False
                else:
                    continue
            if index == 0:
                if array[-1] == array[1]:
                    return False
                else:
                    continue
            if array[index - 1] == "W":
                array[index + 1] = "S"
            else:
                array[index + 1] = "W"
        elif array[index] == "W" and not s[index]:
            if index == n - 1:
                if array[index-1] != array[0]:
                    return False
                else:
                    continue
            if index == 0:
                if array[-1] != array[1]:
                    return False
                else:
                    continue
            array[index + 1] = array[index - 1]
    return array


n = int(input())
s = [True if x == "o" else False for x in list(input())]
ws = ["W", "S"] + ["*" for x in range(n - 2)]
sw = ["S", "W"] + ["*" for x in range(n - 2)]
ss = ["S", "S"] + ["*" for x in range(n - 2)]
ww = ["W", "W"] + ["*" for x in range(n - 2)]

for array in [ws, sw, ss, ww]:
    res = solver(array)
    if not res:
        continue
    else:
        print("".join(res))
        exit()
else:
    print(-1)

Submission status: Accepted

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

#ox
ans = "-1"

for animals in ["SS","SW","WS","WW"]:
    for say in s:
        if (animals[-1] == "S" and say == "o" ) or (animals[-1] == "W" and say == "x"):
            animals += animals[-2]
        elif (animals[-1] == "S" and say == "x"):
            if animals[-2] == "S":
                animals += "W"
            else:
                animals += "S"
        elif (animals[-1] == "W" and say == "o"):
            if animals[-2] == "S":
                animals += "W"
            else:
                animals += "S"
    if animals[:2] == animals[-2:]:
        ans  =animals[1:-1]
print(ans)

Submission status: Accepted

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

li = ["N"]*(n+1)

li[0] = "W"
li[1] = "W"

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

  elif li[i]=="S" and s[i]=="x":
    if li[i-1] == "W":
      li[i+1] = "S"
    else:
      li[i+1] = "W"
     
if li[0]==li[n]:
  if s[0]=="o" and li[1]!=li[n-1]:
    print(str(li[0:n]).replace("[","").replace("]","").replace(",","").replace("'","").replace(" ",""))
    exit()
  if s[0]=="x" and li[1]==li[n-1]:
    print(str(li[0:n]).replace("[","").replace("]","").replace(",","").replace("'","").replace(" ",""))
    exit()

li[0] = "W"
li[1] = "S"

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

  elif li[i]=="S" and s[i]=="x":
    if li[i-1] == "W":
      li[i+1] = "S"
    else:
      li[i+1] = "W"
      
if li[0]==li[n]:     
  if s[0]=="o" and li[1]!=li[n-1]:
    print(str(li[0:n]).replace("[","").replace("]","").replace(",","").replace("'","").replace(" ",""))
    exit()
  if s[0]=="x" and li[1]==li[n-1]:
    print(str(li[0:n]).replace("[","").replace("]","").replace(",","").replace("'","").replace(" ",""))
    exit()

li[0] = "S"
li[1] = "W"

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

  elif li[i]=="S" and s[i]=="x":
    if li[i-1] == "W":
      li[i+1] = "S"
    else:
      li[i+1] = "W"
      
if li[0]==li[n]:     
  if s[0]=="o" and li[1]==li[n-1]:
    print(str(li[0:n]).replace("[","").replace("]","").replace(",","").replace("'","").replace(" ",""))
    exit()
  if s[0]=="x" and li[1]!=li[n-1]:
    print(str(li[0:n]).replace("[","").replace("]","").replace(",","").replace("'","").replace(" ",""))
    exit()

li[0] = "S"
li[1] = "S"

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

  elif li[i]=="S" and s[i]=="x":
    if li[i-1] == "W":
      li[i+1] = "S"
    else:
      li[i+1] = "W"
      
if li[0]==li[n]:     
  if s[0]=="o" and li[1]==li[n-1]:
    print(str(li[0:n]).replace("[","").replace("]","").replace(",","").replace("'","").replace(" ",""))
    exit()
  if s[0]=="x" and li[1]!=li[n-1]:
    print(str(li[0:n]).replace("[","").replace("]","").replace(",","").replace("'","").replace(" ",""))
    exit()
    
print(-1)

Submission status: Accepted

Solution code:
N=int(input())
S=list(input())
S.append(S[0])
S.append(S[1])

L1=["S","S"]
L2=["S","W"]
L3=["W","S"]
L4=["W","W"]

flag=0

for i in range(1,len(S)-1):
    if L1[i]=="S":
        if S[i]=="o" and L1[i-1]=="S":
            L1.append("S")
        elif S[i]=="o" and L1[i-1]=="W":
            L1.append("W")
        elif S[i]=="x" and L1[i-1]=="S":
            L1.append("W")
        elif S[i]=="x" and L1[i-1]=="W":
            L1.append("S")
    else:
        if S[i]=="o" and L1[i-1]=="S":
            L1.append("W")
        elif S[i]=="o" and L1[i-1]=="W":
            L1.append("S")
        elif S[i]=="x" and L1[i-1]=="S":
            L1.append("S")
        elif S[i]=="x" and L1[i-1]=="W":
            L1.append("W")
if L1[0]==L1[len(L1)-2] and L1[1]==L1[len(L1)-1]:
    L1=L1[:N]
    print("".join(L1))
    exit()
    
for i in range(1,len(S)-1):
    if L2[i]=="S":
        if S[i]=="o" and L2[i-1]=="S":
            L2.append("S")
        elif S[i]=="o" and L2[i-1]=="W":
            L2.append("W")
        elif S[i]=="x" and L2[i-1]=="S":
            L2.append("W")
        elif S[i]=="x" and L2[i-1]=="W":
            L2.append("S")
    else:
        if S[i]=="o" and L2[i-1]=="S":
            L2.append("W")
        elif S[i]=="o" and L2[i-1]=="W":
            L2.append("S")
        elif S[i]=="x" and L2[i-1]=="S":
            L2.append("S")
        elif S[i]=="x" and L2[i-1]=="W":
            L2.append("W")
if L2[0]==L2[len(L2)-2] and L2[1]==L2[len(L2)-1]:
    L2=L2[:N]
    print("".join(L2))
    exit()
    
for i in range(1,len(S)-1):
    if L3[i]=="S":
        if S[i]=="o" and L3[i-1]=="S":
            L3.append("S")
        elif S[i]=="o" and L3[i-1]=="W":
            L3.append("W")
        elif S[i]=="x" and L3[i-1]=="S":
            L3.append("W")
        elif S[i]=="x" and L3[i-1]=="W":
            L3.append("S")
    else:
        if S[i]=="o" and L3[i-1]=="S":
            L3.append("W")
        elif S[i]=="o" and L3[i-1]=="W":
            L3.append("S")
        elif S[i]=="x" and L3[i-1]=="S":
            L3.append("S")
        elif S[i]=="x" and L3[i-1]=="W":
            L3.append("W")
if L3[0]==L3[len(L3)-2] and L3[1]==L3[len(L3)-1]:
    L3=L3[:N]
    print("".join(L3))
    exit()
    
for i in range(1,len(S)-1):
    if L4[i]=="S":
        if S[i]=="o" and L4[i-1]=="S":
            L4.append("S")
        elif S[i]=="o" and L4[i-1]=="W":
            L4.append("W")
        elif S[i]=="x" and L4[i-1]=="S":
            L4.append("W")
        elif S[i]=="x" and L4[i-1]=="W":
            L4.append("S")
    else:
        if S[i]=="o" and L4[i-1]=="S":
            L4.append("W")
        elif S[i]=="o" and L4[i-1]=="W":
            L4.append("S")
        elif S[i]=="x" and L4[i-1]=="S":
            L4.append("S")
        elif S[i]=="x" and L4[i-1]=="W":
            L4.append("W")
if L4[0]==L4[len(L4)-2] and L4[1]==L4[len(L4)-1]:
    L4=L4[:N]
    print("".join(L4))
    exit()

print(-1)

Submission status: Accepted

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

ans = '-1'
# 4 pattern of last-first animals
for animals in ['SS', 'SW', 'WS', 'WW']:
    for say in s:
        if (animals[-1] == 'S') != ((say == 'o') != (animals[-2] == 'S')):
            animals += 'S'
        else:
            animals += 'W'
    if animals[:2] == animals[-2:]:
        ans = animals[1:-1]

print(ans)

Submission status: Accepted

Solution code:
def another(t):
    if t == "W":
        return "S"
    else:
        return "W"


def ok(t1, t2, t3, op):
    if (op == "o" and t2 == "S") or (op == "x" and t2 == "W"):
        return t1 == t3
    else:
        return t1 != t3

def check(ans):
    for i in range(n - 2):
        c = s[i]
        t = ans[i]
        if (c == "o" and t == "S") or (c == "x" and t == "W"):
            ans[i + 1] = ans[i - 1]
        else:
            ans[i + 1] = another(ans[i - 1])
    t1, t2, t3, t4 = ans[-3], ans[-2], ans[-1], ans[0]
    return ok(t1, t2, t3, s[-2]) and ok(t2, t3, t4, s[-1])

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

for head, tail in (("S", "S"), ("S", "W"), ("W", "S"), ("W", "W")):
    ans = [""] * n
    ans[0] = head
    ans[-1] = tail
    if check(ans):
        print(*ans, sep="")
        break
else:
    print(-1)

Submission status: Accepted

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

"""
参考：https://img.atcoder.jp/arc069/editorial.pdf
"""

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

def verify(t):
    # 2か所決まれば芋づる式に全て定まる
    for i in range(1, N-1):
        # 羊がoと言ってるor狼がxと言ってる
        if t[i] == 'S' and s[i] == 'o' or t[i] == 'W' and s[i] == 'x':
            # 両隣は同じ
            if t[i-1] == 'S':
                t[i+1] = 'S'
            else:
                t[i+1] = 'W'
        # 逆
        else:
            # 両隣は違う
            if t[i-1] == 'S':
                t[i+1] = 'W'
            else:
                t[i+1] = 'S'
    # 終点手前 - 終点 - 始点、の辻褄が合ってるか検証する
    if t[-1] == 'S' and s[-1] == 'o' or t[-1] == 'W' and s[-1] == 'x':
        if not (t[-2] == 'S' and t[0] == 'S' or t[-2] == 'W' and t[0] == 'W'):
            return False
    else:
        if not (t[-2] == 'S' and t[0] == 'W' or t[-2] == 'W' and t[0] == 'S'):
            return False
    # 終点 - 始点 - 始点の次、の辻褄が合ってるか検証する
    if t[0] == 'S' and s[0] == 'o' or t[0] == 'W' and s[0] == 'x':
        if not (t[-1] == 'S' and t[1] == 'S' or t[-1] == 'W' and t[1] == 'W'):
            return False
    else:
        if not (t[-1] == 'S' and t[1] == 'W' or t[-1] == 'W' and t[1] == 'S'):
            return False
    return True

# 2か所決める方法4通り
for a, b in [('S', 'S'), ('W', 'W'), ('S', 'W'), ('W', 'S')]:
    t = [''] * N
    t[0] = a
    t[1] = b
    if verify(t): 
        print(''.join(t))
        exit()
print(-1)

Submission status: Accepted

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

animals_ans = []
# sheep = 1, wolf = 0
def hypo(sheep, ans, w):
    animals = []
    for _ in range(N):
        animals.append(-1)
    animals[0] = sheep
    if sheep + ans != 1:
        if w == 0:
            animals[N-1] = 1
            animals[1] = 1
        else:
            animals[N-1] = 0
            animals[1] = 0
    else:
        if w == 0:
            animals[N-1] = 0
            animals[1] = 1
        else:
            animals[N-1] = 1
            animals[1] = 0
    for n in range(1, N):
        if (animals[n] == 1 and S[n] == 'o') or  (animals[n] == 0 and S[n] == 'x'):
            if n == N-2 and animals[n+1] != animals[n-1]:
                return 0
            elif n == N-1:
                if animals[n-1] != animals[0]:
                    return 0
                else:
                    return animals
            else:
                animals[n+1] = animals[n-1]
        else:
            if n == N-2 and animals[n+1] == animals[n-1]:
                return 0
            elif n == N-1:
                if animals[n-1] == animals[0]:
                    return 0
                else:
                    return animals
            else:
                animals[n+1] = 1 - animals[n-1]

def arr2str(arr):
    st = ''
    for n in arr:
        if n == 1:
            st += 'S'
        else:
            st += 'W'
    return st

ans = 1 if S[0] == 'o' else 0

# how to print the answer...
animals_ans = hypo(1, ans, 0)
if animals_ans == 0:
    animals_ans = hypo(1, ans, 1)
    if animals_ans == 0:
        animals_ans = hypo(0, ans, 0)
        if animals_ans == 0:
            animals_ans = hypo(0, ans, 1)
            if animals_ans == 0:
                print(-1)
            else:
                print(arr2str(animals_ans))
        else:
            print(arr2str(animals_ans))
    else:
        print(arr2str(animals_ans))
else:
    print(arr2str(animals_ans))

Submission status: Accepted

Solution code:
n = int(input())
s = input()
sw4li = ["SS", "SW", "WS", "WW"]
t = ""
for v in sw4li:
    t = ""
    t += v
    for i in range(1, len(s)):
        if t[-2] == "S" and t[-1] == "S":
            if s[i] == "o":
                t += "S"
            elif s[i] == "x":
                t += "W"
        elif t[-2] == "S" and t[-1] == "W":
            if s[i] == "o":
                t += "W"
            elif s[i] == "x":
                t += "S"
        elif t[-2] == "W" and t[-1] == "S":
            if s[i] == "o":
                t += "W"
            elif s[i] == "x":
                t += "S"
        elif t[-2] == "W" and t[-1] == "W":
            if s[i] == "o":
                t += "S"
            elif s[i] == "x":
                t += "W"
    if t[-1] == t[0]:
        if t[-1] == "S" and t[1] == "S":
            if s[0] == "o":
                if t[-2] == "S":
                    print(t[:-1])
                    exit()
            elif s[0] == "x":
                if t[-2] == "W":
                    print(t[:-1])
                    exit()
        elif t[-1] == "S" and t[1] == "W":
            if s[0] == "o":
                if t[-2] == "W":
                    print(t[:-1])
                    exit()
            elif s[0] == "x":
                if t[-2] == "S":
                    print(t[:-1])
                    exit()
        elif t[-1] == "W" and t[1] == "S":
            if s[0] == "o":
                if t[-2] == "W":
                    print(t[:-1])
                    exit()
            elif s[0] == "x":
                if t[-2] == "S":
                    print(t[:-1])
                    exit()
        elif t[-1] == "W" and t[1] == "W":
            if s[0] == "o":
                if t[-2] == "S":
                    print(t[:-1])
                    exit()
            elif s[0] == "x":
                if t[-2] == "W":
                    print(t[:-1])
                    exit()
print(-1)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
import itertools

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n = II()
S = [c == 'o' for c in SI()]
S += S[:2]

SW = {'S': 'W', 'W': 'S'}
for a1, a2 in itertools.product('SW', repeat=2):
    M = [a1, a2]
    for i in range(n):
        if S[i + 1]:
            M.append(M[-2] if M[-1] == 'S' else SW[M[-2]])
        else:
            M.append(M[-2] if M[-1] == 'W' else SW[M[-2]])

    if M[0] == M[-2] and M[1] == M[-1]:
        print(*M[:-2], sep='')
        exit()

print(-1)