Problem:


Score : 500 points

Problem Statement

Snuke, who loves animals, built a zoo.

There are N animals in this zoo. They are conveniently numbered 1 through N, and arranged in a circle.
The animal numbered i (2≤i≤N-1) is adjacent to the animals numbered i-1 and i+1. Also, the animal numbered 1 is adjacent to the animals numbered 2 and N, and the animal numbered N is adjacent to the animals numbered N-1 and 1.

There are two kinds of animals in this zoo: honest sheep that only speak the truth, and lying wolves that only tell lies.

Snuke cannot tell the difference between these two species, and asked each animal the following question: "Are your neighbors of the same species?" The animal numbered i answered s_i. Here, if s_i is o, the animal said that the two neighboring animals are of the same species, and if s_i is x, the animal said that the two neighboring animals are of different species.

More formally, a sheep answered o if the two neighboring animals are both sheep or both wolves, and answered x otherwise.
Similarly, a wolf answered x if the two neighboring animals are both sheep or both wolves, and answered o otherwise.

Snuke is wondering whether there is a valid assignment of species to the animals that is consistent with these responses. If there is such an assignment, show one such assignment. Otherwise, print -1.

Constraints

3 ≤ N ≤ 10^{5}

s is a string of length N consisting of o and x.

Input

The input is given from Standard Input in the following format:

N
s

Output

If there does not exist an valid assignment that is consistent with s, print -1.
Otherwise, print an string t in the following format. The output is considered correct if the assignment described by t is consistent with s.

t is a string of length N consisting of S and W.

If t_i is S, it indicates that the animal numbered i is a sheep. If t_i is W, it indicates that the animal numbered i is a wolf.

Sample Input 1

6
ooxoox

Sample Output 1

SSSWWS

For example, if the animals numbered 1, 2, 3, 4, 5 and 6 are respectively a sheep, sheep, sheep, wolf, wolf, and sheep, it is consistent with their responses. Besides, there is another valid assignment of species: a wolf, sheep, wolf, sheep, wolf and wolf.

Let us remind you: if the neiboring animals are of the same species, a sheep answers o and a wolf answers x. If the neiboring animals are of different species, a sheep answers x and a wolf answers o.

Sample Input 2

3
oox

Sample Output 2

-1

Print -1 if there is no valid assignment of species.

Sample Input 3

10
oxooxoxoox

Sample Output 3

SSWWSSSWWS



Sample input:
6
ooxoox


Sample output:
SSSWWS

Submission status: Accepted

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

inv = {'S': 'W', 'W': 'S'}
# o と x
def check(t):
    for i in range(2, n):
        if t[i-1] == 'S':
            if s[i-1] == 'o':
                t.append(t[i-2])
            else:
                t.append(inv[t[i-2]])
        else:
            if s[i-1] == 'o':
                t.append(inv[t[i-2]])
            else:
                t.append(t[i-2])

    if t[0] == 'S':
        if s[0] == 'o' and t[1] != t[-1]:
            return "-1"
        elif s[0] == 'x' and t[1] == t[-1]:
            return "-1"
    else:
        if s[0] == 'o' and t[1] == t[-1]:
            return "-1"
        elif s[0] == 'x' and t[1] != t[-1]:
            return "-1"

    if t[-1] == 'S':
        if s[-1] == 'o' and t[0] != t[-2]:
            return "-1"
        elif s[-1] == 'x' and t[0] == t[-2]:
            return "-1"
    else:
        if s[-1] == 'o' and t[0] == t[-2]:
            return "-1"
        elif s[-1] == 'x' and t[0] != t[-2]:
            return "-1"

    return ''.join(t)

ans = "-1"
for t in [['S', 'S'], ['S', 'W'], ['W', 'S'], ['W', 'W']]:
    res = check(t)
    if res != "-1":
        ans = res
        break

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
s = input()
for t0, t1 in ("SS", "SW", "WS", "WW"):
    t = [""] * N
    t[0] = t0
    t[1] = t1
    for i in range(2, N):
        if t[i-2] == t[i-1]:
            t[i] = "S" if s[i-1] == "o" else "W"
        else:
            t[i] = "W" if s[i-1] == "o" else "S"
    if t[-2] == t[-1]:
        if t[0] != ("S" if s[-1] == "o" else "W"):
            continue
    else:
        if t[0] != ("W" if s[-1] == "o" else "S"):
            continue
    if t[-1] == t[0]:
        if t[1] != ("S" if s[0] == "o" else "W"):
            continue
    else:
        if t[1] != ("W" if s[0] == "o" else "S"):
            continue
    print("".join(t))
    exit()
print(-1)

Submission status: Accepted

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

def judgment(animal):
    #print(animal)
    for i in range(N):
        left = i-1
        right = i+1
        if i == 0:
            left = -1
        if i == N - 1:
            right = 0
        if animal[i] == "S" and animal[left] != animal[right] and s[i] == "o":
            return False
        elif animal[i] == "S" and animal[left] == animal[right] and s[i] == "x":
            return False
        elif animal[i] == "W" and animal[left] == animal[right] and s[i] == "o":
            return False
        elif animal[i] == "W" and animal[left] != animal[right] and s[i] == "x":
            return False
    return True

def set_animal(animal1 , animal2):
    animal_round = [animal1,animal2]
    for i in range(2,N):
        if animal_round[i-2] == "S" and animal_round[i-1] == "S":
            if s[i-1] == "o":
                animal_round.append("S")
            elif s[i-1] == "x":
                animal_round.append("W")
        elif animal_round[i-2] == "S" and animal_round[i-1] == "W":
            if s[i-1] == "o":
                animal_round.append("W")
            elif s[i-1] == "x":
                animal_round.append("S")
        elif animal_round[i-2] == "W" and animal_round[i-1] == "S":
            if s[i-1] == "o":
                animal_round.append("W")
            elif s[i-1] == "x":
                animal_round.append("S")
        elif animal_round[i-2] == "W" and animal_round[i-1] == "W":
            if s[i-1] == "o":
                animal_round.append("S")
            elif s[i-1] == "x":
                animal_round.append("W")
    return animal_round


list = [["S","S"],["W","S"],["S","W"],["W","W"]]
for e in list:
    animal_round = set_animal(e[0],e[1])
    flag = judgment(animal_round)
    #print(animal_round)
    if flag:
        break

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

Submission status: Accepted

Solution code:
# ABC055D - Menagerie (ARC069D)
def check(a: int, b: int) -> list:
    ret, cur, prev = [], a, b
    for i in S:
        ret += [cur]
        if cur ^ (i == "o"):
            prev, cur = cur, prev ^ 1  # both are different
        else:
            prev, cur = cur, prev  # both neighbors are the same
    flg = cur == a and prev == b  # check the consistency of input and result
    return ret if flg else []


def main():
    global S
    N = int(input())
    S = input().rstrip()
    for a in range(2):
        for b in range(2):
            ans = check(a, b)
            if ans:
                print("".join("S" if i else "W" for i in ans), sep="")
                return
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC055D - Menagerie (ARC069D)
def check(a: int, b: int) -> list:
    ret, cur, prev = [], a, b
    for i in S:
        ret += [cur]
        if cur ^ (i == "o"):
            prev, cur = cur, prev ^ 1  # both are different
        else:
            prev, cur = cur, prev  # both neighbors are the same
    flg = cur == a and prev == b  # check the consistency of input and result
    return ret if flg else []


def main():
    global S
    N = int(input())
    S = input().rstrip()
    for a in range(2):
        for b in range(2):
            ans = check(a, b)
            if ans:
                print(*["S" if i else "W" for i in ans], sep="")
                return
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC055D - Menagerie (ARC069D)
def check(a: str, b: str) -> str:
    ret, cur, prev = "", a, b
    for i in S:
        ret += cur
        if (cur == "S" and i == "o") or (cur == "W" and i == "x"):
            prev, cur = cur, prev  # both neighbors are the same
        elif (cur == "S" and i == "x") or (cur == "W" and i == "o"):
            x = "W" if prev == "S" else "S"  # both are different
            prev, cur = cur, x
    flg = cur == a and prev == b  # check the consistency of input and result
    return ret if flg else ""


def main():
    global S
    N = int(input())
    S = input().rstrip()
    for a in ("S", "W"):
        for b in ("S", "W"):
            ans = check(a, b)
            if ans:
                print(ans)
                return
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
s=input().rstrip()
start=['SS','SW','WS','WW']
import sys
for k in start:
    ans=[k[0],k[1]]
    for i in range(2,n):
        if (ans[i-2]=='S' and ans[i-1]=='S' and s[i-1]=='o') or (ans[i-2]=='S' and ans[i-1]=='W' and s[i-1]=='x') or (ans[i-2]=='W' and ans[i-1]=='S' and s[i-1]=='x') or (ans[i-2]=='W' and ans[i-1]=='W' and s[i-1]=='o'):
            ans.append('S')
        else:
            ans.append('W')
    if (s[0]=='o' and ans[0]=='S') or (s[0]=='x' and ans[0]=='W'):
        if ans[1]==ans[n-1]:
            pass
        else:
            continue
    else:
        if ans[1]==ans[n-1]:
            continue
    if (s[n-1]=='o' and ans[n-1]=='S') or (s[n-1]=='x' and ans[n-1]=='W'):
        if ans[0]==ans[n-2]:
            pass
        else:
            continue
    else:
        if ans[0]==ans[n-2]:
            continue
    for i in ans:
        print(i,end='')
    sys.exit()
print(-1)

Submission status: Accepted

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

  # S: 1, W: 0
  for a0, a1 in ((0, 0), (0, 1), (1, 0), (1, 1)):
    l = [a0, a1]

    for c in s[1:] + s[0]:
      if c == 'o':
        a0, a1 = a1, not (a0 ^ a1)
      else:
        a0, a1 = a1, (a0 ^ a1)
      l.append(a1)

    if (l[0] == a0) and (l[1] == a1):
      print(''.join('WS'[i] for i in l[:-2]))
      exit()

  print(-1)

if __name__ == '__main__':
  main()

Submission status: Accepted

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

  # S: 1, W: 0
  for a0, a1 in ((0, 0), (0, 1), (1, 0), (1, 1)):
    l = [a0, a1]

    for c in s[1:] + s[0]:
      if c == 'o':
        a0, a1 = a1, not (a0 ^ a1)
      else:
        a0, a1 = a1, (a0 ^ a1)
      l.append(a1)

    if (l[0] == a0) and (l[1] == a1):
      print(''.join('S' if i else 'W' for i in l[:-2]))
      exit()

  print(-1)

if __name__ == '__main__':
  main()

Submission status: Accepted

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

def main():
  # S: 1, W: 0
  for a0, a1 in ((0, 0), (0, 1), (1, 0), (1, 1)):
    l = [a0, a1]

    for c in s[1:]:
      if c == 'o':
        a0, a1 = a1, not (a0 ^ a1)
      else:
        a0, a1 = a1, (a0 ^ a1)
      l.append(a1)

    if (l[0] == l[-2]) and (l[1] == l[-1]):
      print(''.join('S' if i == 1 else 'W' for i in l[:-2]))
      exit()

  print(-1)

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
def main():
  N = int(input())
  s = input()
  s += s[0]

  # S: 1, W: 0
  for a0, a1 in ((0, 0), (0, 1), (1, 0), (1, 1)):
    l = [a0, a1]

    for c in s[1:]:
      if c == 'o':
        a0, a1 = a1, not (a0 ^ a1)
      else:
        a0, a1 = a1, (a0 ^ a1)
      l.append(a1)

    if (l[0] == l[-2]) and (l[1] == l[-1]):
      print(''.join('S' if i == 1 else 'W' for i in l[:-2]))
      exit()

  print(-1)

if __name__ == '__main__':
  main()

Submission status: Accepted

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

# S: 1, W: 0
for a0, a1 in ((0, 0), (0, 1), (1, 0), (1, 1)):
  l = [a0, a1]

  for c in s[1:]:
    if c == 'o':
      a0, a1 = a1, not (a0 ^ a1)
    else:
      a0, a1 = a1, (a0 ^ a1)
    l.append(a1)

  if (l[0] == l[-2]) and (l[1] == l[-1]):
    print(''.join('S' if i == 1 else 'W' for i in l[:-2]))
    exit()

print(-1)

Submission status: Accepted

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

# S: 1, W: 0
for a0, a1 in ((0, 0), (0, 1), (1, 0), (1, 1)):
  l = [a0, a1]

  for c in s[1:]:
    if c == 'o':
      a0, a1 = a1, not (a0 ^ a1)
    else:
      a0, a1 = a1, (a0 ^ a1)
    l.append(a1)

  if (l[0] == l[-2]) and (l[1] == l[-1]):
    s = ''.join('S' if i == 1 else 'W' for i in l[:-2])
    print(s)
    exit()

print(-1)

Submission status: Accepted

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

# S: 1, W: 0
for a0, a1 in ((0, 0), (0, 1), (1, 0), (1, 1)):
  l = [a0, a1]

  for i in range(1, N + 1):
    if s[i] == 'o':
      a0, a1 = a1, not (a0 ^ a1)
    else:
      a0, a1 = a1, (a0 ^ a1)
    l.append(a1)

  if (l[0] == l[-2]) and (l[1] == l[-1]):
    s = ''.join(['S' if i == 1 else 'W' for i in l[:-2]])
    print(s)
    exit()

print(-1)

Submission status: Accepted

Solution code:
N = int(input())
s = input()
s += s[0]
l = [0] * (N + 2)

# S: 1, W: 0
for a0, a1 in ((0, 0), (0, 1), (1, 0), (1, 1)):
  l[0], l[1] = a0, a1

  for i in range(1, N + 1):
    if s[i] == 'o': l[i + 1] = not (l[i] ^ l[i - 1])
    else: l[i + 1] = l[i] ^ l[i - 1]

  if (l[0] == l[-2]) and (l[1] == l[-1]):
    print(*['S' if i == 1 else 'W' for i in l[:-2]], sep='')
    exit()

print(-1)

Submission status: Accepted

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

# S: 1, W: 0
for a0, a1 in ((0, 0), (0, 1), (1, 0), (1, 1)):
  l = [a0, a1]

  for i in range(1, N + 1):
    if s[i] == 'o': l.append(not (l[i] ^ l[i - 1]))
    else: l.append(l[i] ^ l[i - 1])

  if (l[0] == l[-2]) and (l[1] == l[-1]):
    s = ''.join(['S' if i == 1 else 'W' for i in l[:-2]])
    print(s)
    exit()

print(-1)

Submission status: Accepted

Solution code:
N = int(input())
s = input()
l = [1] * N

# S: 1, W: 0
for a0, a1 in ((0, 0), (0, 1), (1, 0), (1, 1)):
  l[0] = a0
  l[1] = a1

  for i in range(1, N - 1):
    if s[i] == 'o':
      if l[i] == 1:
        l[i + 1] = l[i - 1]
      else:
        l[i + 1] = not l[i - 1]
    else:
      if l[i] == 1:
        l[i + 1] = not l[i - 1]
      else:
        l[i + 1] = l[i - 1]
  
  if s[-1] == 'o':
    if l[-1] == 1:
      flag = l[0] == l[-2]
    else:
      flag = l[0] != l[-2]
  else:
    if l[-1] == 1:
      flag = l[0] != l[-2]
    else:
      flag = l[0] == l[-2]
  if flag:
    if s[0] == 'o':
      if l[0] == 1:
        flag = l[-1] == l[1]
      else:
        flag = l[-1] != l[1]
    else:
      if l[0] == 1:
        flag = l[-1] != l[1]
      else:
        flag = l[-1] == l[1]

  if flag:
    s = ''.join(['S' if i == 1 else 'W' for i in l])
    print(s)
    exit()

print(-1)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
ss="SS"
sw="SW"
ws="WS"
ww="WW"
def f(t,c):
    if t=="o":
        if c[-2:]=="SS" or c[-2:]=="WW":
            return c+"S"
        else:
            return c+"W"
    else:
        if c[-2:]=="SW" or c[-2:]=="WS":
            return c+"S"
        else:
            return c+"W"
for i in s[1:n-1]:
    ss=f(i,ss)
    sw=f(i,sw)
    ws=f(i,ws)
    ww=f(i,ww)
def a(s,c):
    if f(s[-1],c[-2:])[2]!=c[0]:
        return 0
    if f(s[0],c[-1]+c[0])[2]!=c[1]:
        return 0
    return 1
for i in [ss,sw,ws,ww]:
    if a(s,i):
        print(i)
        break
else:
    print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, s: str):

    for SW in [[1, 1], [0, 1], [0, 0], [1, 0]]:
        for c in s[1:]:
            if SW[-1] == 1:
                if c == 'o':
                    SW.append(SW[-2])
                else:
                    SW.append(1-SW[-2])
            else:
                if c == 'o':
                    SW.append(1-SW[-2])
                else:
                    SW.append(SW[-2])
        if SW[0] == SW[-1]:
            if ((SW[0] == 1) and (s[0] == 'o') and (SW[-2] == SW[1]))\
               or ((SW[0] == 1) and (s[0] == 'x') and (SW[-2] != SW[1]))\
               or ((SW[0] == 0) and (s[0] == 'o') and (SW[-2] != SW[1]))\
               or ((SW[0] == 0) and (s[0] == 'x') and (SW[-2] == SW[1])):
                print("".join("WS"[sw] for sw in SW[:-1]))
                return

    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 = input()
ls = ['SS','SW','WS','WW']
ok = -1
for ind,i in enumerate(S):
    if(ind==0):continue
    if(ind==N-1):break
    for indj,j in enumerate(ls):
        if(i=='o'):
            if(j[ind]=='S'):
                ls[indj] += j[ind-1]
            else:
                ls[indj] += 'W' if j[ind-1]=='S' else 'S'
        else:
            if(j[ind]=='S'):
                ls[indj] += 'W' if j[ind-1]=='S' else 'S'

            else:
                ls[indj] += j[ind-1]
for num,l in enumerate(ls):
    flag = True
    for ind,i in enumerate(S):
        if(ind==0):
            a = l[-1]
            b = l[1]
        elif(ind==N-1):
            a = l[-2]
            b = l[0]
        else:
            a = l[ind-1]
            b = l[ind+1]
        if(i=='o'):
            if(l[ind]=='S'):
                flag&=(a==b)
            else:
                flag&=(a!=b)
        else:
            if(l[ind]=='S'):
                flag&=(a!=b)
            else:
                flag&=(a==b)
        if(not flag):
            break
    if(flag):
        ok = num
        break
if(ok==-1):
    print(-1)
else:
    print(ls[ok])

Submission status: Accepted

Solution code:

N = int(input())
s = input()
s = list(s)
s.append(s[0])
SW01 = [[0, 0],[0, 1],[1, 0],[1, 1]]


for i in range(4):
	SW = []
	SW.append(SW01[i][0])
	SW.append(SW01[i][1])
	for loc in range(1, N + 1):
		if s[loc] == "o":
			SW.append(SW[loc-1]^SW[loc])
		else:
			SW.append(SW[loc - 1] ^ (SW[loc]^1))
	if SW[0] == SW[-2] and SW[1] == SW[-1]:
		SW2 = []
		for i in range(N):
			if SW[i] == 0:
				SW2.append('S')
			else:
				SW2.append('W')
		print("".join(SW2))
		exit()


print(-1)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    n = II()
    ans = n * 800
    print(ans-(n//15)*200)
    return

#B
def B():
    n = II()
    print(math.factorial(n)%mod)
    return

#C
def C():
    n, m = LI()
    if n >= m // 2:
        print(m // 2)
        return
    else:
        m -= 2 * n
        print(n+m//4)
    return

#D
def D():
    n = II()
    ss = S()
    s = ["S", "W"]
    for i1 in s:
        for i2 in s:
            ans = [i1, i2]
            for i in range(1, n):
                if ans[i] == "S":
                    if ss[i] == "o":
                        ans.append(ans[i - 1])
                    else:
                        if ans[i - 1] == "S":
                            ans.append("W")
                        else:
                            ans.append("S")
                else:
                    if ss[i] == "x":
                        ans.append(ans[i - 1])
                    else:
                        if ans[i - 1] == "S":
                            ans.append("W")
                        else:
                            ans.append("S")

            if ans[0] != ans[-1]:
                continue
            del ans[-1]

            if ans[0] == "S":
                if ss[0] == "o":
                    if ans[1] != ans[-1]:
                        continue
                else:
                    if ans[1] == ans[-1]:
                        continue
            else:
                if ss[0] == "x":
                    if ans[1] != ans[-1]:
                        continue
                else:
                    if ans[1] == ans[-1]:
                        continue

            for i in range(1, n - 1):
                if ans[i] == "S":
                    if ss[i] == "o":
                        if ans[i - 1] != ans[i + 1]:
                            continue
                    else:
                        if ans[i - 1] == ans[i + 1]:
                            continue
                else:
                    if ss[i] == "x":
                        if ans[i - 1] != ans[i + 1]:
                            continue
                    else:
                        if ans[i - 1] == ans[i + 1]:
                            continue

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

            print("".join(ans))
            return

    print(-1)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
""" abc055_a """

import sys

H = pow(10, 9) + 7

def _main():
    _n = int(sys.stdin.readline())
    answers = list(map(lambda a: a == 'o', sys.stdin.readline()))

    # ooxoox
    # S-----
    # a[0] = o: SS---S
    # a[1] = o: SSS--S
    # a[2] = x: SSSW-S
    # a[3] = o: SSSWWS
    # a[4] = o: SSSWWS OK
    # a[5] = x: SSSWWS OK

    def _evaluate(zoo_first, zoo_last):

        zoo = [None] * _n

        zoo[0] = zoo_first == 'S'
        zoo[_n-1] = zoo_last == 'S'

        for i in range(0, _n):
            same = answers[i] if zoo[i] else not answers[i]
            next_z = zoo[(i-1)%_n] if same else not zoo[(i-1)%_n]
            if zoo[(i+1)%_n] is None:
                zoo[(i+1)%_n] = next_z
            else:
                if zoo[(i+1)%_n] != next_z:
                    return -1

        return zoo

    for _f, _l in [['S', 'S'], ['W', 'W'], ['S', 'W'], ['W', 'S'],]:
        result = _evaluate(_f, _l)
        if -1 != result:
            print(_format(result))
            return

    print(-1)

def _format(result):
    return ''.join(map(lambda e: 'S' if e else 'W', result))

if __name__ == '__main__':
    _main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

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

#print(s)
def solve(a,b): #a: n-1th b:0th 
    res = [a,b]
    for i in s:
        if i == "o":
            c = (res[-1]+res[-2])%2
        else:
            c = (1+res[-1]+res[-2])%2
        res.append(c)
#    print(a,res)
    if res[-2] == a and res[-1] == b:
        ans = ["W" if i else "S" for i in res[1:-1]]
        print("".join(ans))
        exit()
    
    
for a in range(2):
    for b in range(2):
        solve(a,b)
        
print(-1)

Submission status: Accepted

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

for ans in ["SS", "SW", "WW", "WS"]:
    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:]:
        print(ans[:n])
        exit()

print(-1)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
L=[]
done=False

for c in s:
    if c=="o":
        L.append(0)
    else:
        L.append(1)

ans="00"
for i in range(3,n+1):
    ans+=str((int(ans[i-3])+int(ans[i-2])+L[i-2])%2)

#print(ans)
if int(ans[0])==(int(ans[-1])+int(ans[-2])+L[-1])%2 and int(ans[1])==(int(ans[0])+int(ans[-1])+L[0])%2:
    pass

else:    
    ans="01"
    for i in range(3,n+1):
        ans+=str((int(ans[i-3])+int(ans[i-2])+L[i-2])%2)
    
    #print(ans)
    if int(ans[0])==(int(ans[-1])+int(ans[-2])+L[-1])%2 and int(ans[1])==(int(ans[0])+int(ans[-1])+L[0])%2:
        pass
    else:    
        ans="10"
        for i in range(3,n+1):
            ans+=str((int(ans[i-3])+int(ans[i-2])+L[i-2])%2)
        
        #print(ans)
        if int(ans[0])==(int(ans[-1])+int(ans[-2])+L[-1])%2 and int(ans[1])==(int(ans[0])+int(ans[-1])+L[0])%2:
            pass
        else:    
            ans="11"
            for i in range(3,n+1):
                ans+=str((int(ans[i-3])+int(ans[i-2])+L[i-2])%2)
            
            #print(ans)
            pass
            if int(ans[0])==(int(ans[-1])+int(ans[-2])+L[-1])%2 and int(ans[1])==(int(ans[0])+int(ans[-1])+L[0])%2:
                #print("!")
                pass
            else:
                print(-1)
                done=True

if not done:
    pri=""
    for c in ans:
        if c =="0":
            pri+="S"
        else:
            pri+="W"
    print(pri)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *

n = int(input())
s = input()
s = [0 if t == 'o' else 1 for t in s]
x = [None]*n
for a, b in [(0,0), (0,1), (1,0), (1,1)]:
    x[0], x[1] = a, b
    flag = 1
    for i in range(2, n):
        x[i] = 1^x[i-2] if x[i-1]^s[i-1] else x[i-2]
    for i in range(n-1):
        if (x[i]^s[i])^(x[i-1] != x[i+1]):
            flag = 0
            break
    if flag and ((x[n-1]^s[n-1])^(x[n-2] != x[0])) == 0:
        x = ['S' if t == 0 else 'W' for t in x]
        print(*x, sep='')
        exit()
print(-1)

Submission status: Accepted

Solution code:

def check(aaa, flg):
    if flg == 'o':
        if aaa[1]:
            if aaa[0] == aaa[2]:
                return 1
        else:
            if aaa[0] != aaa[2]:
                return 1
    else:
        if aaa[1]:
            if aaa[0] != aaa[2]:
                return 1
        else:
            if aaa[0] == aaa[2]:
                return 1
    return 0


def main():
    num = int(input())
    data = list(input())

    dp = [[-1 for i in range(num)] for j in range(4)]

    flg = [0 for i in range(4)]

    if data[0] == 'o':
        dp[0][0], dp[0][num - 1], dp[0][1] = 1, 1, 1
        dp[1][0], dp[1][num - 1], dp[1][1] = 1, 0, 0
        dp[2][0], dp[2][num - 1], dp[2][1] = 0, 1, 0
        dp[3][0], dp[3][num - 1], dp[3][1] = 0, 0, 1
    else:
        dp[0][0], dp[0][num - 1], dp[0][1] = 0, 1, 1
        dp[1][0], dp[1][num - 1], dp[1][1] = 0, 0, 0
        dp[2][0], dp[2][num - 1], dp[2][1] = 1, 1, 0
        dp[3][0], dp[3][num - 1], dp[3][1] = 1, 0, 1

    for i in range(1, num - 2):
        now_data = data[i]
        for j in range(4):
            if now_data == 'o':
                if dp[j][i] == dp[j][i - 1]:
                    dp[j][i + 1] = 1
                else:
                    dp[j][i + 1] = 0
            else:
                if dp[j][i] == dp[j][i - 1]:
                    dp[j][i + 1] = 0
                else:
                    dp[j][i + 1] = 1

    ans_flg = -1

    for i in range(4):
        aaa = [dp[i][num - 3], dp[i][num - 2], dp[i][num - 1]]
        bbb = [dp[i][num - 2], dp[i][num - 1], dp[i][0]]

        # print(aaa, bbb, dp[i])

        if check(aaa, data[num - 2]) and check(bbb, data[num - 1]):
            ans_flg = i

    # for i in range(4):
    #     print(dp[i])

    if ans_flg == -1:
        print(-1)
    else:
        dict = {1:'S', 0:'W'}
        for i in range(num):
            print(dict[dp[ans_flg][i]], end='')
            if i == num - 1:
                print()




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

def read_input():
    n = int(input())
    s = input()
    ox = [c for c in s]

    return n, ox


def check_order(sw, ox):
    pre = -1
    post = 1

    for a, c in zip(sw, ox):
        if a == 'S':
            if c == 'o':
                if sw[pre] != sw[post]:
                    return False
            if c == 'x':
                if sw[pre] == sw[post]:
                    return False
        elif a == 'W':
            if c == 'o':
                if sw[pre] == sw[post]:
                    return False
            if c == 'x':
                if sw[pre] != sw[post]:
                    return False

        pre += 1
        post += 1

        if post == len(sw):
            post = 0

    return True


def get_animal(a, flip):
    if flip:
        if a == 'S':
            return 'W'
        else:
            return 'S'

    return a


def submit():
    n, ox = read_input()

    # test1
    sw = ['S', 'S']
    for i in range(1, n - 1):
        if sw[i] == 'S':
            if ox[i] == 'o':
                sw.append(get_animal(sw[i - 1], flip = False))
            else:
                sw.append(get_animal(sw[i - 1], flip = True))
        elif sw[i] == 'W':
            if ox[i] == 'o':
                sw.append(get_animal(sw[i - 1], flip = True))
            else:
                sw.append(get_animal(sw[i - 1], flip = False))

    if check_order(sw, ox):
        print(''.join(sw))
        return

    # test2
    sw = ['S', 'W']
    for i in range(1, n - 1):
        if sw[i] == 'S':
            if ox[i] == 'o':
                sw.append(get_animal(sw[i - 1], flip = False))
            else:
                sw.append(get_animal(sw[i - 1], flip = True))
        elif sw[i] == 'W':
            if ox[i] == 'o':
                sw.append(get_animal(sw[i - 1], flip = True))
            else:
                sw.append(get_animal(sw[i - 1], flip = False))

    if check_order(sw, ox):
        print(''.join(sw))
        return

    # test3
    sw = ['W', 'S']
    for i in range(1, n - 1):
        if sw[i] == 'S':
            if ox[i] == 'o':
                sw.append(get_animal(sw[i - 1], flip = False))
            else:
                sw.append(get_animal(sw[i - 1], flip = True))
        elif sw[i] == 'W':
            if ox[i] == 'o':
                sw.append(get_animal(sw[i - 1], flip = True))
            else:
                sw.append(get_animal(sw[i - 1], flip = False))

    if check_order(sw, ox):
        print(''.join(sw))
        return

    # test4
    sw = ['W', 'W']
    for i in range(1, n - 1):
        if sw[i] == 'S':
            if ox[i] == 'o':
                sw.append(get_animal(sw[i - 1], flip = False))
            else:
                sw.append(get_animal(sw[i - 1], flip = True))
        elif sw[i] == 'W':
            if ox[i] == 'o':
                sw.append(get_animal(sw[i - 1], flip = True))
            else:
                sw.append(get_animal(sw[i - 1], flip = False))

    if check_order(sw, ox):
        print(''.join(sw))
        return

    print(-1)


if __name__ == '__main__':
    submit()