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: Wrong Answer

Solution code:
a = int(input())
s = input()
l = len(s)
target = [None for x in s]
target[0] = True
target[1] = True


def fill(b, n, i):
    if s[i] == "o":
        target[b] = target[n] if target[i] else not target[n]
    else:
        target[b] = not target[n] if target[i] else target[n]


def jud(b, n, i):
    if s[i] == "o":
        return target[b] == (target[n] if target[i] else not target[n])
    else:
        return target[b] == (not target[n] if target[i] else target[n])
    

def result(s1, s2):
    global target
    target = [None for x in s]
    target[0] = s1
    target[1] = s2
    for i in range(1, len(s)):
        b, n = i - 1, (i + 1) % l
        fill(n, b, i)
    return jud(n, b, i)

for p in [[True, True], [True, False], [False, True], [False, False]]:
    if result(*p):
        print("".join(["S" if x else "W" for x in target]))
        break
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Here your code !

a = 6
s = "ooxoox"
l = len(s)
target = [None for x in s]
target[0] = True
target[1] = True


def fill(b, n, i):
    if s[i] == "o":
        target[b] = target[n] if target[i] else not target[n]
    else:
        target[b] = not target[n] if target[i] else target[n]


def jud(b, n, i):
    if s[i] == "o":
        return target[b] == (target[n] if target[i] else not target[n])
    else:
        return target[b] == (not target[n] if target[i] else target[n])
    

def result(s1, s2):
    global target
    target = [None for x in s]
    target[0] = s1
    target[1] = s2
    for i in range(1, len(s)):
        b, n = i - 1, (i + 1) % l
        fill(n, b, i)
    return jud(n, b, i)

for p in [[True, True], [True, False], [False, True], [False, False]]:
    if result(*p):
        print("".join(["S" if x else "W" for x in target]))
        break
else:
    print(-1)

Submission status: Wrong Answer

Solution code:

a = int(input())
s = input()
l = len(s)
target = [None for x in s]
target[0] = True
target[1] = True


def fill(b, n, i):
    if s[i] == "o":
        target[b] = target[n] if target[i] else not target[n]
    else:
        target[b] = not target[n] if target[i] else target[n]


def jud(b, n, i):
    if s[i] == "o":
        return target[b] == (target[n] if target[i] else not target[n])
    else:
        return target[b] == (not target[n] if target[i] else target[n])
    

def result(s1, s2):
    global target
    target = [None for x in s]
    target[0] = True
    target[1] = True
    for i in range(1, len(s)):
        b, n = i - 1, (i + 1) % l
        fill(n, b, i)
    return jud(n, b, i)

for p in [[True, True], [True, False], [False, True], [False, False]]:
    if result(*p):
        print("".join(["S" if x else "W" for x in target]))
        break
else:
    print(-1)

Submission status: Wrong Answer

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

s_flag = [1 if s[i]=='o' else -1 for i in range(N)]

def find_pattern(init_t_flag):
    for i in range(2, len(s_flag)):
        init_t_flag.append(init_t_flag[i-2]*init_t_flag[i-1]*s_flag[i-1])
    first_t_flag = init_t_flag[-2] * init_t_flag[-1] * s_flag[-1]
    if init_t_flag[0] == first_t_flag:
        return init_t_flag
    else:
        return -1

def output_result():
    res_SS = find_pattern([1,1])
    if res_SS != -1:
        res = ['S' if res_SS[i]==1 else 'W' for i in range(N)]
        return("".join(res))

    res_SW = find_pattern([1, -1])
    if res_SW != -1:
        res = ['S' if res_SW[i]==1 else 'W' for i in range(N)]
        return("".join(res))

    res_WS = find_pattern([-1,1])
    if res_WS != -1:
        res = ['S' if res_WS[i]==1 else 'W' for i in range(N)]
        return("".join(res))

    res_WW = find_pattern([-1, -1])
    if res_WW != -1:
        res = ['S' if res_WW[i]==1 else 'W' for i in range(N)]
        return("".join(res))

    return("-1")

print(output_result())

Submission status: Wrong Answer

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

s_flag = [1 if s[i]=='o' else -1 for i in range(N)]

def find_pattern(init_t_flag):
    for i in range(2, len(s_flag)):
        init_t_flag.append(init_t_flag[i-2]*init_t_flag[i-1]*s_flag[i-1])
    last_t_flag = init_t_flag[0] * init_t_flag[1] * s_flag[0]
    if init_t_flag[-1] == last_t_flag:
        return init_t_flag
    else:
        return -1

def output_result():
    res_SS = find_pattern([1,1])
    if res_SS != -1:
        res = ['S' if res_SS[i]==1 else 'W' for i in range(N)]
        return("".join(res))

    res_SW = find_pattern([1, -1])
    if res_SW != -1:
        res = ['S' if res_SW[i]==1 else 'W' for i in range(N)]
        return("".join(res))

    res_WS = find_pattern([-1,1])
    if res_WS != -1:
        res = ['S' if res_WS[i]==1 else 'W' for i in range(N)]
        return("".join(res))

    res_WW = find_pattern([-1, -1])
    if res_WW != -1:
        res = ['S' if res_WW[i]==1 else 'W' for i in range(N)]
        return("".join(res))

    return("-1")

print(output_result())

Submission status: Wrong Answer

Solution code:
def main():
    N = int(raw_input())
    s= raw_input()
    ans = ["SS", "SW", "WS", "WW"]
    for n in range(4):
          for i in range(N-2):
              ans[n] += pred(ans[n][i], ans[n][i+1], s[i+1])
          if check(ans[n] ,s, N):
              return ans[n]
    return -1

def pred(a_a, a_b, s_b):
    if((a_b == 'S' and s_b == 'o' ) or (a_b == 'W' and s_b == 'x')):
        return a_a
    else:
        if(a_a == 'S'):
            return 'W'
        else:
            return 'S'

def check(ans, s, N):
    if((ans[N-1] == 'S' and s[N-1] == 'o') or (ans[N-1] == 'W' and s[N-1] == 'x')):
        if ans[0] != ans[N-2]:
            return False
    else:
          if ans[0] == ans[N-2]:
            return False
    return True
print main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(raw_input())
    s= raw_input()
    
    ans1 = "SS"
    for i in range(N-2):
        ans1 += pred(ans1[i], ans1[i+1], s[i+1])
    if check(ans1 ,s, N):
        return ans1
    
    ans2 = "SW"
    for i in range(N-2):
        ans2 += pred(ans2[i], ans2[i+1], s[i+1])
    if check(ans2 ,s, N):
        return ans2

    ans3 = "WS"
    for i in range(N-2):
        ans3 += pred(ans3[i], ans3[i+1], s[i+1])
    if check(ans3 ,s, N):
        return ans3
    
    ans4 = "WW"
    for i in range(N-2):
        ans4 += pred(ans4[i], ans4[i+1], s[i+1])
    if check(ans4 ,s, N):
        return ans4

    return -1

def pred(a_a, a_b, s_b):
    if((a_b == 'S' and s_b == 'o' ) or (a_b == 'W' and s_b == 'x')):
        return a_a
    else:
        if(a_a == 'S'):
            return 'W'
        else:
            return 'S'

def check(ans, s, N):
    if((ans[N-1] == 'S' and s[N-1] == 'o') or (ans[N-1] == 'W' and s[N-1] == 'x')):
        if ans[0] != ans[N-2]:
            return False
    else:
          if ans[0] == ans[N-2]:
            return False
    return True
print main()

Submission status: Wrong Answer

Solution code:
n = int(raw_input().rstrip("\n"))
ring = raw_input().rstrip("\n")
ring = ring + ring[0]

answers = []
answers.append([True,True])
answers.append([True,False])
answers.append([False,True])
answers.append([False,False])

sw = {True:"S",False:"W"}
result = None
for answer in answers:
  for i in xrange(n):
    if (answer[i+1] == True and ring[i+1] == "o") or (answer[i+1] == False and ring[i+1] == "w"):
       answer.append(answer[i])
    else:
       answer.append(not answer[i])   

  if answer[0:2] == answer[-2:]:
    result= "".join([sw[is_sheep] for is_sheep in answer[:n]])
    break
    #print result

if result:
  print result
else:
  print -1

Submission status: Wrong Answer

Solution code:
n = int(raw_input().rstrip("\n"))
ring = raw_input().rstrip("\n")
ring = ring + ring[0]

answers = []
answers.append([True,True])
answers.append([True,False])
answers.append([False,True])
answers.append([False,False])

sw = {True:"s",False:"w"}
result = None
for answer in answers:
  for i in xrange(n):
    if (answer[i+1] == True and ring[i+1] == "o") or (answer[i+1] == False and ring[i+1] == "w"):
       answer.append(answer[i])
    else:
       answer.append(not answer[i])   

  if answer[0:2] == answer[-2:]:
    result= "".join([sw[is_sheep] for is_sheep in answer[:n]])
    break
    #print result

if result:
  print result
else:
  print -1

Submission status: Wrong Answer

Solution code:
import sys

cin = sys.stdin
# cin = open("in.txt", "r")

N = int(cin.readline())
s = cin.readline().rstrip()

first_two = ['SS', 'SW', 'WS', 'WW']
SW_dict = {'S': 'W', 'W': 'S'}

idList = ['S']*(N+1)
for f2 in first_two:
    idList[0] = f2[0]
    idList[1] = f2[1]
    for i in range(2, N+1):
        if idList[i-1]=='S':
            if s[i-1]=='o':
                idList[i] = idList[i-2]
            else:
                idList[i] = SW_dict[idList[i-2]]

        else: # i-1=='W'
            if s[i-1]=='o':
                idList[i] = SW_dict[idList[i-2]]
            else:
                idList[i] = idList[i-2]
    if idList[N]==idList[0]:
        print(''.join(idList[:-1]))
        exit(0)

print(-1)

Submission status: Wrong Answer

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

for b in ['SS','SW','WW','WS']:
 a=[]
 a.append(s[0]+b[0])
 a.append(s[1]+b[1])
 for i in range(N-1):
  if a[i+1]=='oS' or a[i+1]=='xW':
     a.append(s[i+2]+b[i])
     b+=b[i]
  else:
     if b[i]=='S':
        a.append(s[i+2]+'W')
        b+='W'
     else:
        a.append(s[i+2]+'S')
        b+='S'
 if b[-1]!=b[0]:
   dd=0
 else:
   print(b[0:-1])
   dd=1
   break
if dd==0:
   print(-1)

Submission status: Wrong Answer

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

for b in ['SS','SW','WW','SS']:
 a=[]
 a.append(s[0]+b[0])
 a.append(s[1]+b[1])
 for i in range(N-1):
  if a[i+1]=='oS' or a[i+1]=='xW':
     a.append(s[i+2]+b[i])
     b+=b[i]
  else:
     if b[i]=='S':
        a.append(s[i+2]+'W')
        b+='W'
     else:
        a.append(s[i+2]+'S')
        b+='S'
 if b[-1]!=b[0]:
   dd=0
 else:
   print(b[0:-1])
   dd=1
   break
if dd==0:
   print(-1)

Submission status: Wrong Answer

Solution code:
N=int(input())
s=input()
s+=s[0]
a=[]
a.append(s[0]+'S')
a.append(s[1]+'S')
b='SS'
for i in range(N-1):
  if a[i+1]=='oS' or a[i+1]=='xW':
     a.append(s[i+2]+b[i])
     b+=b[i]
  else:
     if b[i]=='S':
        a.append(s[i+2]+'W')
        b+='W'
     else:
        a.append(s[i+2]+'S')
        b+='S'
if b[-1]=='W':
  print(-1)
else:
  print(b[0:-1])

Submission status: Wrong Answer

Solution code:
N = int(input())
S2 = input()
S = [-1 for i in range(N)]
for i in range(N):
    if S2[i] == 'o':
        S[i] = 0
    else:
        S[i] = 1
A = [-1 for i in range(N)]
hatu = [[0,0],[1,1],[0,1],[1,0]]
flag = 0
for j in range(4):
    A[0] = hatu[j][0]
    A[1] = hatu[j][1]
    for i in range(N-1):
        if A[i] == 0 and A[i+1] == 0 and S[i+1] == 0:
            ans = 0
        elif A[i] == 0 and A[i+1] == 0 and S[i+1] == 1:
            ans = 1
        elif A[i] == 0 and A[i+1] == 1 and S[i+1] == 0:
            ans = 1
        elif A[i] == 0 and A[i+1] == 1 and S[i+1] == 1:
            ans = 0
        elif A[i] == 1 and A[i+1] == 0 and S[i+1] == 0:
            ans = 1
        elif A[i] == 1 and A[i+1] == 0 and S[i+1] == 1:
            ans = 0
        elif A[i] == 1 and A[i+1] == 1 and S[i+1] == 0:
            ans = 0
        else:
            ans = 1
        if i == N-2 and A[0] == ans:
            flag = 1
        A[(i+2)%N] = ans
    #print(A)
    if flag == 1:
        break
if flag == 0:
    print(-1)
else:
    Ans = []
    for a in A:
        if a == 0:
            print('S',end='\0')
        else:
            print('W',end='\0')
    print()

Submission status: Wrong Answer

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

def test(bm, b0):
    b = [True] * N
    b[-1] = bm
    b[0] = b0
    for i in range(N - 1):
        b[i + 1] = b[i - 1]
        if b[i] ^ (s[i] == 'o'):
            b[i + 1] = not b[i + 1]
    
    if b[N - 1] == ((s[N - 1] == 'o') == (b[N - 2] == b[0])):
        printB(b)
        return True
    else:
        return False

def printB(b):
    for i in range(N):
        print('S' if b[i] else 'W', end='')
        
    print()
    

def main():
    if test(True, True):
        return
    elif test(True, False):
        return
    elif test(False, True):
        return
    elif test(False, False):
        return

    print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def not_animal(animal):
    if animal == 'S':
        return 'W'
    return 'S'

def f(prev, animal, ans):
    x = g(animal, ans)
    if not x:
        return not_animal(prev)
    return prev

def g(animal, ans):
    ret = True
    if ans == 'x':
        ret = False

    if animal == 'S':
        return ret
    return not ret
    
def is_equal(x, y):
    return x == (y[0] == y[1])

N = int(input())
s = input()
circles = [['.' for i in range(N)] for i in range(4)]

_init = [('S', 'S'), ('W', 'W'),('S', 'W'), ('W', 'S')]

if s[0] == 'x':
    _init[:2], _init[2:] = _init[2:], _init[:2]

circles[0][0] = circles[1][0] = 'S'
circles[2][0] = circles[3][0] = 'W'

for i in range(4):
    circles[i][1], circles[i][-1] = _init[i]

for i in range(4):
    for j in range(1, N-2):
        circles[i][j+1] = f(circles[i][j-1], circles[i][j], s[j])
#    print(circles[i])


for i in range(4):
    for j in range(N):
        if not is_equal(g(circles[i][j], s[j]), (circles[i][j-1], circles[i][-1 if j==N-1 else j+1])):
            break
    else:
        print(''.join(circles[i]))
        break
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
n=int(raw_input())
s=raw_input()
state=[['W','S'],['S','W'],['W','W'],['S','S']]
for now in state:
    for i in xrange(1,n):
        if s[i]=="o":
            if now[i]=="S":
                now.append(now[i-1])
            else:
                if now[i-1]=="S":
                    now.append("W")
                else:
                    now.append("S")
        else:
            if now[i]=="W":
                now.append(now[i-1])
            else:
                if now[i-1]=="S":
                    now.append("W")
                else:
                    now.append("S")
    ok=False
    if now[0]==now[n]:
        if s[0]=="o":
            if now[0]=="S":
                if now[1]==now[n-1]:
                    ok=True
            else:
                if now[1]!=now[n-1]:
                    ok=True
        else:
            if now[0]=="O":
                if now[1]==now[n-1]:
                    ok=True
            else:
                if now[1]!=now[n-1]:
                    ok=True
    if ok:
        print "".join(now[0:n])
        exit()
print -1

Submission status: Wrong Answer

Solution code:
def not_animal(animal):
    if animal == 'S':
        return 'W'
    return 'S'

def f(prev, animal, ans):
    x = g(animal, ans)
    if not x:
        return not_animal(prev)
    return prev

def g(animal, ans):
    ret = True
    if ans == 'x':
        ret = False

    if animal == 'S':
        return ret
    return not ret
    
def is_equal(x, y):
    return x == (y[0] == y[1])

N = int(input())
s = input()
circles = [['.' for i in range(N)] for i in range(4)]

_init = [('S', 'S'), ('W', 'W'),('S', 'W'), ('W', 'S')]

if s[0] == 'x':
    _init[:2], _init[2:] = _init[2:], _init[:2]

circles[0][0] = circles[1][0] = 'S'
circles[2][0] = circles[3][0] = 'W'

for i in range(4):
    circles[i][1], circles[i][-1] = _init[i]

for i in range(4):
    for j in range(1, N-2):
        circles[i][j+1] = f(circles[i][j-1], circles[i][j], s[j])
#    print(circles[i])


for i in range(4):
    if is_equal(g(circles[i][-1], s[-1]), (circles[i][-2], circles[i][0])) and is_equal(g(circles[i][-2], s[-1]), (circles[i][-3], circles[i][-2])):
        print(''.join(circles[i]))
        break
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
n=int(raw_input())
s=raw_input()
state=[['S','S'],['W','S'],['S','W'],['W','W']]
for now in state:
    for i in xrange(1,n):
        if s[i]=="o":
            if now[i]=="S":
                now.append(now[i-1])
            else:
                if now[i-1]=="S":
                    now.append("W")
                else:
                    now.append("S")
        else:
            if now[i]=="W":
                now.append(now[i-1])
            else:
                if now[i-1]=="S":
                    now.append("W")
                else:
                    now.append("S")
    if now[0]==now[n]:
        print "".join(now[0:n])
        exit()
print -1

Submission status: Wrong Answer

Solution code:
import sys

n = int(raw_input())
s = raw_input()

first = ['SS', 'SW', 'WS', 'WW']

for f in first:
    ans = f
    for i in [i+1 for i in range(n-1)]:
        if ans[-1] == 'S':
            if ans[-2] == 'S':
                if s[i] == 'o':
                    ans += 'S'
                else:
                    ans += 'W'
            else:
                if s[i] == 'o':
                    ans += 'W'
                else:
                    ans += 'S'
        else:
            if ans[-2] == 'S':
                if s[i] == 'o':
                    ans += 'W'
                else:
                    ans += 'S'
            else:
                if s[i] == 'o':
                    ans += 'S'
                else:
                    ans += 'W'
    if ans[0] == ans[-1]:
        print ans[0:n]
        sys.exit(0)

print -1

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()


def main():
    n = II()
    s = [c == 'o' for c in S()]
    for k in ['SS','SW','WS','WW']:
        r = k
        for i in range(1,n-1):
            t = r[-1]
            t2 = r[-2]
            if (t == 'S' and t2 == 'S' and s[i]) or (
                t == 'S' and t2 == 'W' and not s[i]) or (
                t == 'W' and t2 == 'S' and not s[i]) or (
                t == 'W' and t2 == 'W' and s[i]):
                r += 'S'
            else:
                r += 'W'
        if ((((r[-1] == 'S' and s[-1]) or (r[-1] == 'W' and not s[-1]))  and  r[-2] == r[0]) or (
            ((r[-1] == 'W' and s[-1]) or (r[-1] == 'S' and not s[-1]))  and r[-2] != r[0])) and (
            (((r[0] == 'S' and s[0]) or (r[0] == 'W' and not s[0]))  and  r[0] == r[1]) or (
            ((r[0] == 'W' and s[0]) or (r[0] == 'S' and not s[0]))  and r[0] != r[1])):
            return r
    return -1

print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()


def main():
    n = II()
    s = [c == 'o' for c in S()]
    for k in ['SS','SW','WS','WW']:
        r = k
        for i in range(1,n-1):
            t = r[-1]
            t2 = r[-2]
            if (t == 'S' and t2 == 'S' and s[i]) or (
                t == 'S' and t2 == 'W' and not s[i]) or (
                t == 'W' and t2 == 'S' and not s[i]) or (
                t == 'W' and t2 == 'W' and s[i]):
                r += 'S'
            else:
                r += 'W'
        if ((((r[-1] == 'S' and s[-1]) or (r[-1] == 'W' and not s[-1]))  and  r[-2] == r[0]) or (
            ((r[-1] == 'W' and s[-1]) or (r[-1] == 'S' and not s[-1]))  and r[-2] != r[0])) and (
            (((r[0] == 'S' and s[0]) or (r[0] == 'W' and not s[0]))  and  r[-1] == r[1]) or (
            ((r[0] == 'W' and s[0]) or (r[0] == 'S' and not s[0]))  and r[0] != r[1])):
            return r
    return -1

print(main())

Submission status: Wrong Answer

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

SHEEP = True
WOLF = False

def check(s, a, b):
    animals = [a, b]
    for c in s[1:]:
        if animals[-1] is SHEEP:
            animals.append(animals[-2] if c == 'o' else not animals[-2])
        else:
            animals.append(animals[-2] if c == 'x' else not animals[-2])

    if a is animals[-1]:
        print(''.join(['S' if a else 'W' for a in animals[:-1]]))
        return True
    else:
        return False

def main():
    input()
    s = input()

    for a in [SHEEP, WOLF]:
        for b in [SHEEP, WOLF]:
            if check(s, a, b):
                return

    print(-1)

main()

Submission status: Wrong Answer

Solution code:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1000000)

N = read()
s = [0 if c == "o" else 1 for c in input()]

ans = [0] * N

for a, b in product([0, 1], [0, 1]):
  ans[0:2] = [a, b]
  for i in range(2, N):
    ans[i] = (ans[i-2] + ans[i-1] + s[i-1]) % 2
  if (ans[N-2] + ans[N-1] + ans[0] + s[N-1]) % 2 == 0:
    print("".join("SW"[ans[i]] for i in range(N)))
    exit()


print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    s=input()
    for ans in ("SS","SW","WS","WW"):
        for c in s[1:]:
            if ans[-1]=="S":
                ans+="W" if (ans[-2]=="W")^(c=="x") else "S"
            else:
                ans+="S" if (ans[-2]=="W")^(c=="x") else "W"
        if ans[0]==ans[-1] and (((ans[0]=="W")^(s[0]=="x"))^(ans[-2]==ans[1])):
            print(ans[:-1])
            sys.exit()
    print(-1)


if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
s = input().rstrip()
for t in ['SS', 'SW', 'WS', 'WW']:
    for i in range(1, N-1):
        if (t[-1] == 'W') ^ (s[i] == 'o') ^ (t[-2] == 'S'):
            t += 'W'
        else:
            t += 'S'
    if (t[-1] == 'W') ^ (s[-1] == 'o') ^ (t[-2] == t[0]):
        continue
    if (t[0] == 'W') ^ (s[0] == 'o') ^ (t[-1] == t[1]):
        continue
    print(t)
    exit()
print(-1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
ans = ""
def next_animal(pre,now,letter):
    if pre == "S" and now == "S" and letter == "o":
        return "S"
    if pre == "S" and now == "S" and letter == "x":
        return "W"
    if pre == "S" and now == "W" and letter == "o":
        return "W"
    if pre == "S" and now == "W" and letter == "x":
        return "S"
    if pre == "W" and now == "S" and letter == "o":
        return "W"
    if pre == "W" and now == "S" and letter == "x":
        return "S"
    if pre == "W" and now == "W" and letter == "o":
        return "S"
    if pre == "W" and now == "W" and letter == "x":
        return "W"

for case in range(4):
    if case == 0:
        ans = "SS"
    if case == 1:
        ans = "SW"
    if case == 2:
        ans = "WS"
    if case == 3:
        ans = "WW"
    for i in range(1,n-1):
        next = next_animal(ans[-1],ans[-2],s[i])
        ans += next
    if ans[-1] == next_animal(ans[1],ans[0],s[0]) and ans[0] == next_animal(ans[-2],ans[-1],s[-1]):
        print(ans)
        exit()

print(-1)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()*2
for a in['SS','SW','WS','WW']:
    for i in range(1,n+1):
        f=a[i]+s[i]
        if f=='So'or'Wx'==f:
            a+=a[i-1]
        else:
            a+=a[i-1].translate({83:87,87:83})
    if a[:2]==a[n:]:
        print(a[:n])
        break
else:
    print(-1)

Submission status: Time Limit Exceeded

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

a = ['SS','SW','WS','WW']

for j in range(len(a)):
    for i in range(1,n-1):
        if s[i]=='x':
            if a[j][i]==a[j][i-1]:
                a[j]+='W'
            else:
                a[j]+='S'
        else:
            if a[j][i]==a[j][i-1]:
                a[j]+='S'
            else:
                a[j]+='W'
    flag = 0
    if (s[-1] == 'x' and a[j][-1]=='S') or (s[-1] == 'o' and a[j][-1]=='W'):
        if a[j][-2] != a[j][0]:
            flag += 1
    else:
        if a[j][-2] == a[j][0]:
            flag += 1
    if (s[0] == 'x' and a[j][0]=='S') or (s[0] == 'o' and a[j][0]=='W'):
        if a[j][-1] != a[j][1]:
            flag += 1
    else:
        if a[j][-1] == a[j][1]:
            flag += 1
    if flag == 2:
        print(a[j])
        exit()

print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache

sys.setrecursionlimit(2*10**5)

# 入力
N = int(input())
s = input()
xs = [
    1 if c == 'o' else
    -1
    for c in s
]


# 動物1と動物2の種別を決め打ちで割り当てて、矛盾がないかを検証する
@lru_cache(maxsize=None)
def f(l, r, i):
    return (
        l if i == 0 else
        r if i == 1 else
        f(l, r, i - 2) * f(l, r, i - 1) * xs[(i - 1) % N]
    )


def g(l, r):
    return ''.join(
        'S' if f(l, r, i) == 1 else
        'W'
        for i in range(N)
    )


ans = (
    g(1, 1) if f(1, 1, N) == 1 and f(1, 1, N + 1) == 1 else
    g(1, -1) if f(1, -1, N) == 1 and f(1, -1, N + 1) == -1 else
    g(-1, 1) if f(-1, 1, N) == -1 and f(-1, 1, N + 1) == 1 else
    g(-1, -1) if f(-1, -1, N) == -1 and f(-1, -1, N + 1) == -1 else
    '-1'
)

# 出力
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
s += s[0]
ans = [''] * (n+1)
rev_dic = {'S':'W', 'W':'S'}
for a0,a1 in zip('SSWW','SWSW'):
    ans[0] = a0
    ans[1] = a1
    for i in range(1,n):
        if(ans[i] == 'S')&(s[i] == 'o'):
            ans[i+1] = ans[i-1]
        elif(ans[i] == 'S')&(s[i] == 'x'):
            ans[i+1] = rev_dic[ans[i-1]]
        elif(ans[i] == 'W')&(s[i] == 'o'):
            ans[i+1] = rev_dic[ans[i-1]]
        elif(ans[i] == 'W')&(s[i] == 'x'):
            ans[i+1] = ans[i-1]
    if(ans[0] == ans[-1]):
        if(ans[0]=='S')&(s[0]=='o')&(ans[n-1]==ans[1]):
            print(''.join(ans[:-1]))
            exit()
        if(ans[0]=='S')&(s[0]=='x')&(ans[n-1]!=ans[1]):
            print(''.join(ans[:-1]))
            exit()
        if(ans[0]=='W')&(s[0]=='o')&(ans[n-1]!=ans[1]):
            print(''.join(ans[:-1]))
            exit()
        if(ans[0]=='W')&(s[0]=='x')&(ans[n-1]==ans[1]):
            print(''.join(ans[:-1]))
            exit()
print(-1)

Submission status: Accepted

Solution code:
N = int(input())
s = input()
s += s[0]
L = ["SS","SW","WS","WW"]

for e in L:
    for k in range(1,N+1):
        if s[k] == "o" and e[-1] == "S":
            e += e[-2]
        elif (s[k] == "x" and e[-1] == "S") or (s[k] == "o" and e[-1] == "W"):
            if e[-2] == "S":
                e += "W"
            else:
                e += "S"
        elif s[k] == "o" and e[-1] == "W":
            if e[-2] == "W":
                e += "S"
            else:
                e += "W"
        else:
            e += e[-2]
    if e[:2] == e[-2:]:
        print(e[:-2])
        exit(0)
print(-1)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/arc069/tasks/arc069_b

from collections import deque

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

# 両方試すかな？ (1が羊(0)のとき，1が狼(1)のとき)
def valid(ans):
    # print(ans)
    for i in range(1, N - 1):
        if S[i] == 'o':
            if ans[i] == 0:
                ans[i + 1] = ans[i - 1]
            else:
                ans[i + 1] = 1 - ans[i - 1]
        else:
            if ans[i] == 0:
                ans[i + 1] = 1 - ans[i - 1]
            else:
                ans[i + 1] = ans[i - 1]

    flag1 = False
    if ans[-1] == 0:
        if S[-1] == 'o':
            flag1 = ans[-2] == ans[0]
        else:
            flag1 = ans[-2] != ans[0]
    else:
        if S[-1] == 'o':
            flag1 = ans[-2] != ans[0]
        else:
            flag1 = ans[-2] == ans[0]

    flag2 = False
    if ans[0] == 0:
        if S[0] == 'o':
            flag2 = ans[1] == ans[-1]
        else:
            flag2 = ans[1] != ans[-1]
    else:
        if S[0] == 'o':
            flag2 = ans[1] != ans[-1]
        else:
            flag2 = ans[1] == ans[-1]
    return flag1 and flag2

for (v0, v1) in [(0, 0), (0, 1), (1, 0), (1, 1)]:
    ans = [-1] * N
    ans[0] = v0
    ans[1] = v1
    flag = valid(ans)
    # print(ans, flag)
    if flag:
        for ch in ans:
            print('S' if ch == 0 else 'W', end='')
        print()
        exit()

print("-1")

Submission status: Accepted

Solution code:
from itertools import product

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

for bfo2, bfo1 in product(['S', 'W'], repeat=2):
    ans = [bfo2, bfo1]
    for i in s:
        if ((bfo1 == 'S' and i == 'o')
                or (bfo1 == 'W' and i == 'x')):
            ans.append(bfo2)
        elif ((bfo1 == 'S' and i == 'x')
                or (bfo1 == 'W' and i == 'o')):
            ans.append(*({'S', 'W'} - {bfo2}))
        bfo1, bfo2 = ans[-1], bfo1
    if ans[:2] == ans[-2:]:
        print(*ans[1:-1], sep='')
        break
else:
    print(-1)