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, s = int(input()), input()

ans = ["" for i in range(n)]


def solve():
    for i in range(n-2):
        if s[i] == "o" and ans[i] == "S" or s[i] == "x" and ans[i] == "W":
            ans[i+1] = ans[i-1]
        elif ans[i-1] == "S":
            ans[i+1] = "W"
        else:
            ans[i+1] = "S"

    for i in range(n):
        if s[i-1] == "o" and ans[i-1] == "S" and ans[i-2] == ans[i]:
            continue
        if s[i-1] == "x" and ans[i-1] == "S" and ans[i-2] != ans[i]:
            continue
        if s[i-1] == "o" and ans[i-1] == "W" and ans[i-2] != ans[i]:
            continue
        if s[i-1] == "x" and ans[i-1] == "W" and ans[i-2] == ans[i]:
            continue

        return False

    return True


def main():
    ans[0] = ans[-1] = "S"
    if solve():
        print("".join(ans))
        exit()

    ans[0], ans[-1] = "S", "W"
    if solve():
        print("".join(ans))
        exit()

    ans[0], ans[-1] = "W", "S"
    if solve():
        print("".join(ans))
        exit()

    ans[0] = ans[-1] = "W"
    if solve():
        print("".join(ans))
        exit()

    print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import product
N = int(input())
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
    x=(ans[N-2]+ans[N-1]+s[N-1])%2
    y=(ans[N-1]+ans[0]+s[0])%2
    if x==ans[0] and y==ans[1]:
        num=['S' if k==0 else'W' for k in ans]
        print(''.join(num))
        sys.exit()
print(-1)

Submission status: Accepted

Solution code:
import collections

res = str()

def make(ans,n,s):
    for i in range(2,n):
        if ans[i-1] == 'S':
            if s[i-1] == 'o':
                ans += ans[i-2]
            else:
                ans += 'S' if ans[i-2] == 'W' else 'W'
        else:
            if s[i-1] == 'o':
                ans += 'S' if ans[i-2] == 'W' else 'W'
            else:
                ans += ans[i-2]
    return ans

def check(ans,s,i):
    if ans[i] == 'S':
        if s[i] == 'o':
            return ans[i-1] == ans[i+1]
        else:
            return ans[i-1] != ans[i+1]
    else:
        if s[i] == 'o':
            return ans[i-1] != ans[i+1]
        else:
            return ans[i-1] == ans[i+1]

def solve():
    n = int(input())
    s = input()
    ans = make("SS",n,s)
    if check(ans,s,0) and check(ans,s,-1):
        print(ans)
        return
    ans = make("SW",n,s)
    if check(ans,s,0) and check(ans,s,-1):
        print(ans)
        return
    ans = make("WS",n,s)
    if check(ans,s,0) and check(ans,s,-1):
        print(ans)
        return
    ans = make("WW",n,s)
    if check(ans,s,0) and check(ans,s,-1):
        print(ans)
        return
    print(-1)
    return

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
for kind1 in range(2):
    for kind2 in range(2):
        T = [0] * (N + 2)
        T[0] = kind1
        T[1] = kind2
        for i in range(1, N + 1):
            if T[i] == 0 and S[i % N] == 'o':
                T[i + 1] = T[i - 1]
            elif T[i] == 0 and S[i % N] == 'x':
                T[i + 1] = T[i - 1] ^ 1
            elif T[i] == 1 and S[i % N] == 'o':
                T[i + 1] = T[i - 1] ^ 1
            else:
                T[i + 1] = T[i - 1]
        if T[0] == T[-2] and T[1] == T[-1]:
            print(''.join("SW"[t] for t in T[:-2]))
            quit()
print(-1)

Submission status: Accepted

Solution code:
def chain(s,p):
  s2=s[1::]+s[0]
  for i in s2:
    if i=='o':
      if p[-1]=='0': p=p+p[-2] 
      else:  p=p+str((int(p[-2])-1)*(-1))
    else:
      if p[-1]=='0': p=p+str((int(p[-2])-1)*(-1))
      else: p=p+p[-2]
  return p

N=int(input())
s=input()
p1='00'
p2='01'
p3='10'
p4='11'
p1=chain(s,p1)
p2=chain(s,p2)
p3=chain(s,p3)
p4=chain(s,p4)
l=[p1,p2,p3,p4]
flag=0
for i in l:
  if i[0]==i[-2] and i[1]==i[-1]:
    flag=1
    i=str(i[0:-2])
    i=i.replace('0','S')
    i=i.replace('1','W')
    print(i)
    break
if flag==0: print('-1')

Submission status: Accepted

Solution code:
import sys

N = int(raw_input())
S = raw_input()

printed = False

for zero_is in range(2):
	for one_is in range(2):
		type = [0 for i in range(N)]
		type[0] = zero_is
		type[1] = one_is
		this_works = True

		for j in range(1, N):
			ind_prev = j - 1
			ind_next = (j + 1) % N

			if S[j] == 'o' and type[j] == 0 or S[j] == 'x' and type[j] == 1:
				type[ind_next] = type[ind_prev]
			else:
				type[ind_next] = not type[ind_prev]

		for j in range(0, N):
			ind_prev = (j + N - 1) % N
			ind_next = (j + 1) % N

			if S[j] == 'o' and type[j] == 0 or S[j] == 'x' and type[j] == 1:
				if type[ind_prev] != type[ind_next]:
					this_works = False
			else:
				if type[ind_prev] == type[ind_next]:
					this_works = False

		if this_works is True and printed is False:
			for i in type:
				if i == 0:
					sys.stdout.write('S')
				else:
					sys.stdout.write('W')
			printed = True

if printed is False:
	print -1
else:
	sys.stdout.write('\n')

Submission status: Accepted

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

ans = ["SS", "SW", "WS", "WW"]

for i in range(4):
    for j in range(1, n + 1):
        if s[j - 1] == "o":
            if ans[i][j] == "S":
                if ans[i][j - 1] == "S":
                    ans[i] += "S"
                else:
                    ans[i] += "W"
            else:
                if ans[i][j - 1] == "S":
                    ans[i] += "W"
                else:
                    ans[i] += "S"
        else:
            if ans[i][j] == "S":
                if ans[i][j - 1] == "S":
                    ans[i] += "W"
                else:
                    ans[i] += "S"
            else:
                if ans[i][j - 1] == "S":
                    ans[i] += "S"
                else:
                    ans[i] += "W"

    if ans[i][0] == ans[i][n] and ans[i][1] == ans[i][n + 1]:
        flag = True
    else:
        flag = False

    if flag:
        idx = i
        break

if flag:
    print(ans[idx][1:n + 1])
else:
    print(-1)

Submission status: Accepted

Solution code:
def menagerie_2():
	n = int(raw_input())
	ans = str(raw_input())

	def check_possibility(at, a):
		re = ['#']*len(a)
		re[0] = at[0]
		re[1] = at[1]
		for i in range(1, n-1):
			if a[i]=='o':
				if re[i]==1:
					re[i+1] = re[i-1]
				else:
					re[i+1] = re[i-1]*-1
			else:
				if re[i]==1:
					re[i+1] = re[i-1]*-1
				else:
					re[i+1] = re[i-1]

		c1 = False
		c2 = False
		if a[0]=='o':
			if re[0]==1 and (re[1]*re[-1]==1):
				c1 = True
			elif re[0]==-1 and (re[1]*re[-1]==-1):
				c1 = True
		else:
			if re[0]==1 and (re[1]*re[-1]==-1):
				c1 = True
			elif re[0]==-1 and (re[1]*re[-1]==1):
				c1 = True
		if a[-1]=='o':
			if re[-1]==1 and (re[0]*re[-2]==1):
				c2 = True
			elif re[-1]==-1 and (re[0]*re[-2]==-1):
				c2 = True
		else:
			if re[-1]==1 and (re[0]*re[-2]==-1):
				c2 = True
			elif re[-1]==-1 and (re[0]*re[-2]==1):
				c2 = True
		if c1 and c2:
			return re
		else:
			return None

	if check_possibility([1,1], ans) is not None:
		op = ['S' if x == 1 else 'W' for x in check_possibility([1,1], ans)]
		print''.join(op)
	elif check_possibility([1,-1], ans) is not None:
		op = ['S' if x == 1 else 'W' for x in check_possibility([1,-1], ans)]
		print''.join(op)
	elif check_possibility([-1,1], ans) is not None:
		op = ['S' if x == 1 else 'W' for x in check_possibility([-1,1], ans)]
		print''.join(op)
	elif check_possibility([-1,-1], ans) is not None:
		op = ['S' if x == 1 else 'W' for x in check_possibility([-1,-1], ans)]
		print''.join(op)
	else:
		print -1


if __name__ == "__main__":
	menagerie_2()

Submission status: Accepted

Solution code:
def solve(pos0_is_sheep, pos1_is_sheep):
    pre_is_sheep = pos1_is_sheep
    prepre_is_sheep = pos0_is_sheep
    ans = [pos0_is_sheep]
    for is_same_neighbors in s[1:]:
        ans.append(pre_is_sheep)
        if pre_is_sheep:
            pre_is_sheep = is_same_neighbors == prepre_is_sheep
            prepre_is_sheep = True
        else:
            pre_is_sheep = is_same_neighbors != prepre_is_sheep
            prepre_is_sheep = False
    if pos0_is_sheep != pre_is_sheep:
        return False
    if pos0_is_sheep and s[0] != (prepre_is_sheep == pos1_is_sheep):
        return False
    if not pos0_is_sheep and s[0] == (prepre_is_sheep == pos1_is_sheep):
        return False
    return ans


n = int(input())
s = [c == 'o' for c in input().strip()]

for pos0_is_sheep, pos1_is_sheep in ((1, 1), (1, 0), (0, 1), (0, 0)):
    result = solve(pos0_is_sheep, pos1_is_sheep)
    if result:
        print(''.join('WS'[is_sheep] for is_sheep in result))
        break
else:
    print(-1)

Submission status: Accepted

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(-1, 1, 0) and jud(0, 2, 1)

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: Accepted

Solution code:
n=int(input())
s=input().replace("o","1 ").replace("x","-1 ")
s=[int(i) for i in s.split()]
s.append(s[0])
a=[0 for i in range(n+2)]
b=[]
for j in [-1,1]:
 for k in [-1,1]:
   a[0]=j
   a[1]=k
   for i in range(1,n+1):
     a[i+1]=a[i]*s[i]*a[i-1]
   b.append("".join([str(ii) for ii in a]).replace("-1","W").replace("1","S"))
c=[]
for i in b:
 if i[0]==i[n] and i[1]==i[n+1]:
   c=i[:n]
   break
if len(c):
 print(c)
else:
 print(-1)

Submission status: Accepted

Solution code:
# coding: utf-8

n_ani = int(input())
l_ans = list(input())


def get_next_animal(pre_ani, now_ani, ans):
    if pre_ani == "S":
        if now_ani == "S":
            if ans == "o":
                return "S"
            else:
                return "W"
        else:
            if ans == "o":
                return "W"
            else:
                return "S"

    else:
        if now_ani == "S":
            if ans == "o":
                return "W"
            else:
                return "S"
        else:
            if ans == "o":
                return "S"
            else:
                return "W"


def solve_question(first_ani, last_ani):
    global l_ani
    l_ani.append(first_ani)
    next_ani = get_next_animal(last_ani, first_ani, l_ans[0])
    l_ani.append(next_ani)
    for i in range(1, (n_ani - 1)):
        next_ani = get_next_animal(l_ani[i - 1], l_ani[i], l_ans[i])
        l_ani.append(next_ani)

    if l_ani[(n_ani - 1)] == last_ani and get_next_animal(l_ani[(n_ani - 2)], l_ani[(n_ani - 1)], l_ans[(n_ani - 1)]) == l_ani[0]:
        return "ok"
    else:
        return "ng"


ng_counter = 0

for i in range(4):
    l_ani = []
    if i == 0:
        fir_ani = "S"
        las_ani = "S"
        if solve_question(fir_ani, las_ani) == "ok":
            print ("".join([i for i in l_ani]))
            break
        else:
            ng_counter += 1

    elif i == 1:
        fir_ani = "S"
        las_ani = "W"
        if solve_question(fir_ani, las_ani) == "ok":
            print ("".join([i for i in l_ani]))
            break
        else:
            ng_counter += 1

    elif i == 2:
        fir_ani = "W"
        las_ani = "S"
        if solve_question(fir_ani, las_ani) == "ok":
            print ("".join([i for i in l_ani]))
            break
        else:
            ng_counter += 1

    elif i == 3:
        fir_ani = "W"
        las_ani = "W"
        if solve_question(fir_ani, las_ani) == "ok":
            print ("".join([i for i in l_ani]))
            break
        else:
            ng_counter += 1

if ng_counter == 4:
    print(-1)

Submission status: Accepted

Solution code:
import itertools,math,bisect,pprint,sys
#N, K = map(int, raw_input().split())
n = input()
s = list(raw_input())
ans = [0 for i in range(n)]
def check():
    b1 = (s[n-1]=="o" and (ans[n-2]+ans[n-1]+ans[0])%2==1)
    b2 = (s[n-1]=="x" and (ans[n-2]+ans[n-1]+ans[0])%2==0)
    b3 = (s[0]=="o" and (ans[n-1]+ans[0]+ans[1])%2==1)
    b4 = (s[0]=="x" and (ans[n-1]+ans[0]+ans[1])%2==0)
    return (b1 or b2) and (b3 or b4)
for i in [[0,0],[0,1],[1,0],[1,1]]:
    ans[0] = i[0]
    ans[1] = i[1]
    for j in range(2,n):
        if s[j-1] == "o":
            ans[j] = (ans[j-2]+ans[j-1]+1)%2
        else:
            ans[j] = (ans[j-2]+ans[j-1])%2
    else:
        if check():
            res = ""
            for i in ans:
                if i == 1:
                    res += "S"
                else:
                    res += "W"
            print res
            sys.exit()
else:
    print -1

Submission status: Accepted

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]
    second_t_flag = init_t_flag[-1] * init_t_flag[0] * s_flag[0]
    if init_t_flag[0] == first_t_flag and init_t_flag[1] == second_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: Accepted

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

N = int(raw_input())
s = raw_input()

res = -1
maru = 0
batsu = 0

for i in range(N):
    if s[i] == 'o':
        maru += 1
    else:
        batsu += 1
#print maru, batsu

revers = {'S':'W', 'W':'S'}
res = ''
patterns = ['SS', 'SW', 'WS', 'WW']

for pattern in patterns:
    res = ''
    flg = 0
    flg2 = 0
    res += pattern
    for i in range(2, N,1):
        if res[i-1] == 'S':
            if s[i-1] == 'o':
                res += res[i-2]
            else:
                res += revers[res[i-2]]
        else:
            if s[i-1] == 'o':
                res += revers[res[i-2]]
            else:
                res += res[i-2]
    if res[0] == 'S':
        if s[0] == 'o':
            if res[-1] == res[1]:
                flg = 1
        else:
            if res[-1] != res[1]:
                flg = 1
    else:
        if s[0] == 'o':
            if res[-1] != res[1]:
                flg = 1
        else:
            if res[-1] == res[1]:
                flg = 1

    if res[-1] == 'S':
        if s[-1] == 'o':
            if res[-2] == res[0]:
                flg2 = 1
        else:
            if res[-2] != res[0]:
                flg2 = 1
    else:
        if s[-1] == 'o':
            if res[-2] != res[0]:
                flg2 = 1
        else:
            if res[-2] == res[0]:
                flg2 = 1

    if flg == 1 and flg2 == 1:
        break

if flg == 0 or flg2 ==0:
    print -1
else:
    print res

Submission status: Accepted

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, 0, N)  and check(ans[n] , s , N-1, 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, i, N):
    if((ans[i] == 'S' and s[i] == 'o') or (ans[i] == 'W' and s[i] == 'x')):
            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
print main()

Submission status: Accepted

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] == "x"):
       answer.append(answer[i])
    else:
       answer.append(not answer[i])   
  #print answer, answer[0:2],answer[-2:]
  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: Accepted

Solution code:
import sys

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

N = int(cin.readline())
s = cin.readline().rstrip()
s = s+s[0]

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


# WA first time for only testing N+1==0
# test case
# 4
# xxxx

idList = ['S']*(N+2)
for f2 in first_two:
    idList[0] = f2[0]
    idList[1] = f2[1]
    for i in range(2, N+2):
        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] and idList[N+1]==idList[1]:
        print(''.join(idList[:-2]))
        exit(0)

print(-1)

Submission status: Accepted

Solution code:
import sys
from itertools import product

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N = int(input())
    S = [0 if i == 'o' else 1 for i in input()]
    
    for i, j in product(range(2), repeat=2):
        pat = [i, j] + [0]*(N - 2)
        for k in range(2, N):
            pat[k] = (S[k - 1] - (pat[k - 1] + pat[k - 2])) % 2

        if S[-1] != (pat[0] + pat[-1] + pat[-2]) % 2:
            continue
        if S[0] != (pat[1] + pat[0] + pat[-1]) % 2:
            continue

        ans = ['S' if pat[k] == 0 else 'W' for k in range(N)]
        print(''.join(ans))
        return None

    print(-1)

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

def readln():
    _res = list(map(int,str(input()).split(' ')))
    return _res

# mark sheep with 0, wolf with 1
# x -> 1, o -> 0
# si = ai-1^ai^ai+1

def cvt(c):
    if c == 'o':
        return 0
    else:
        return 1

def mxor(x1,x2,x3):
    return (x1+x2+x3) % 2

def test():
    a[n] = a[0]
    for i in range(2,n):
        a[i] = mxor(a[i-2],s[i-1],a[i-1])
    if a[0] != mxor(a[n-1],s[0],a[1]):
        return False
    if a[n-1] != mxor(a[n-2],s[n-1],a[n]):
        return False
    return True

def no_answer():
    for a[0] in range(0,2):
        for a[1] in range(0,2):
            if test():
                st = ""
                for x in range(0,n):
                    if a[x] == 0: st = st + 'S'
                    else: st = st + 'W'
                print(st)
                return False
    return True

n = int(input())
s = list(map(cvt,str(input())))
a = [0 for i in range(0,n+1)]
if no_answer():
    print(-1)

# [1, 0, 1, 1, 0, 1, 0, 1, 1, 0]

Submission status: Accepted

Solution code:
n=int(input());s=input();a=['SS','WS','SW','WW']
for i in range(n):
    for j in range(4):a[j]+='SW'[::-1 if s[i]=='o' else 1][a[j][i]==a[j][i+1]]
for i in range(4):
    if a[i][1]==a[i][n+1] and a[i][0] == a[i][n]:print(a[i][1:n+1]);exit()
print(-1)

Submission status: Accepted

Solution code:
def findNextAnimal(oxList, swList, index):
    nextAns = oxList[index]
    before = swList[index-1]
    animal = swList[index]
    nextAnimal = ""
    if(nextAns == "o" and before == "S" and animal == "S"):
        nextAnimal = "S"
    elif(nextAns == "o" and before == "S" and animal == "W"):
        nextAnimal = "W"
    elif(nextAns == "o" and before == "W" and animal == "S"):
        nextAnimal = "W"
    elif(nextAns == "o" and before == "W" and animal == "W"):
        nextAnimal = "S"
    elif(nextAns == "x" and before == "S" and animal == "S"):
        nextAnimal = "W"
    elif(nextAns == "x" and before == "S" and animal == "W"):
        nextAnimal = "S"
    elif(nextAns == "x" and before == "W" and animal == "S"):
        nextAnimal = "S"
    elif(nextAns == "x" and before == "W" and animal == "W"):
        nextAnimal = "W"
    return nextAnimal

def checkList(oxList, swList):
    ans = 0
    if(swList[-1] == "S"):
        if(oxList[-1] == "x" and swList[-2] != swList[0]):
            ans = 1
        elif(oxList[-1] == "o" and swList[-2] == swList[0]):
            ans = 1
    elif(swList[-1] == "W"):
        if(oxList[-1] == "x" and swList[-2] == swList[0]):
            ans = 1
        elif(oxList[-1] == "o" and swList[-2] != swList[0]):
            ans = 1
            
    ans2 = 0    
    if(swList[0] == "S"):
        if(oxList[0] == "x" and swList[1] != swList[-1]):
            ans2 = 1
        elif(oxList[0] == "o" and swList[1] == swList[-1]):
            ans2 = 1
    elif(swList[0] == "W"):
        if(oxList[0] == "x" and swList[1] == swList[-1]):
            ans2 = 1
        elif(oxList[0] == "o" and swList[1] != swList[-1]):
            ans2 = 1
    
    return ans*ans2

try:
    while True:  
        n = raw_input().strip().upper()
        oxList = raw_input().strip().lower()
        ans = -1
        for s0 in ["S", "W"]:
            for s1 in ["S","W"]:
                swList = [0]*int(n)
                swList[0] = s0
                swList[1] = s1
                for i in range(2, int(n)):
                    nextAnimal = findNextAnimal(oxList, swList, i-1)
                    swList[i] = nextAnimal
                    flag = checkList(oxList, swList)
                    if(flag == 1):
                        ans = ""
                        for s in swList:
                            ans += s
        print ans
                        
except EOFError:
    pass

Submission status: Accepted

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

import itertools


def allocate(n, ss):
    ts = [s == "o" for s in ss]
    for x0, x1 in itertools.product((True, False), repeat=2):
        xs = [None for _ in range(n + 1)]
        xs[0] = xs[-1] = x0
        xs[1] = x1
        for i in range(n - 2):
            diff = xs[i + 1] ^ ts[i + 1]
            xs[i + 2] = xs[i] ^ diff
        for i in range(n):
            left = xs[(i - 1) % n]
            right = xs[(i + 1) % n]
            diff = xs[i] ^ ts[i]
            if diff != (left != right):
                break
        else:
            return xs[:n]
    return None


def main():
    n = int(input())
    ss = input()
    res = allocate(n, ss)
    if res is None:
        print(-1)
    else:
        print("".join("S" if x else "W" for x in res))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
s = list(map(lambda x: x == 'o', input()))

# try all 4 cases

from itertools import product
for a,b in product((True,False), repeat=2):
  x,y = a,b
  for p in s:
    a,b = b, a^b^p

  if x == a and y == b:
    temp = [None]*N
    for i,p in enumerate(s):
      temp[i] = b
      a,b = b, a^b^p
    print(''.join('S' if t else 'W' for t in temp))
    exit()

print(-1)

Submission status: Accepted

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

SHEEP = True
WOLF = False

def check(s, a, b):
    animals = [a, b]
    s = s[1:] + s[0]
    for c in s:
        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[-2] and b is animals[-1]:
        print(*['WS'[int(a)] for a in animals[:-2]], sep='')
        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: Accepted

Solution code:
import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N = int(input())
    S = [True if i == 'o' else False for i in input()]
    # debug(S, locals())

    for i, j in [(False, False), (False, True), (True, False), (True, True)]:
        pat = [i, j]
        for k in range(2, N):
            if pat[k - 1]:
                if S[k - 1]:
                    pat.append(pat[k - 2])
                else:
                    pat.append(not pat[k - 2])
            else:
                if S[k - 1]:
                    pat.append(not pat[k - 2])
                else:
                    pat.append(pat[k - 2])

        # debug(pat, locals())

        for k in range(N):
            if pat[k]:
                if S[k] != is_same(pat, k, N):
                    break
            else:
                if S[k] == is_same(pat, k, N):
                    break
        else:
            ans = ['S' if pat[k] else 'W' for k in range(N)]
            print(''.join(ans))
            return None

    print(-1)

def is_same(pat, i, N):
    return pat[(i - 1) % N] == pat[(i + 1) % N]

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys

def check(pos, s, SW):
    N = len(s)
    pre  = (pos - 1) % N
    post = (pos + 1) % N
    if(s[pos] == 'o' and SW[pre]+SW[pos]+SW[post] in ['WSW', 'SSS', 'SWW', 'WWS']):
        return True
    if(s[pos] == 'x' and SW[pre]+SW[pos]+SW[post] in ['WSS', 'SSW', 'SWS', 'WWW']):
        return True
    return False

if __name__=="__main__":
    N = int(input())
    s = input()
    li = ["SS", "SW", "WS", "WW"]
    for SW in li:
        for i in range(1,N-1):
            if(s[i] == 'o'):
                if(SW[i] == 'W'):
                    if(SW[i-1] == 'W'):
                        SW += 'S'
                    else:
                        SW += 'W'
                else:
                    SW += SW[i-1]
            else:
                if(SW[i] == 'S'):
                    if(SW[i-1] == 'W'):
                        SW += 'S'
                    else:
                        SW += 'W'
                else:
                    SW += SW[i-1]

        if(check(0, s, SW) and check(N-1, s, SW)):
            print(SW)
            sys.exit()
    print(-1)

Submission status: Accepted

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 - 2):
        b[i + 1] = b[i - 1]
        if b[i] ^ (s[i] == 'o'):
            b[i + 1] = not b[i + 1]
    
    if b[-2] == ((s[-2] == 'o') == (b[-3] == b[-1])) and b[-1] == ((s[-1] == 'o') == (b[-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()