TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P5750
  • Problem
  • P5750狼人杀
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 1S,256M
    Description

      何老板组织信竞队的同学们玩一种"狼人杀"游戏。
      信竞队有N名同学,他们围坐成一圈,顺时针编号1到N (即i号同学与i-1和i+1号同学相邻。N号同学与N-1号同学和1号同学相邻)。
      游戏开始前,何老板离开机房(回避),每个同学都抽取了一张游戏牌。游戏牌有两种,狼人和农夫。抽到狼人牌的同学扮演狼人,抽到农夫牌的同学扮演农夫。每个同学都知道相邻同学扮演的角色。抽牌结束后,何老板回到机房。
      何老板的任务是要确定每个同学扮演的角色。
      他可以对每个同学提问:“跟你相邻的两个同学是同类吗?”,对于第i号同学,若与他相邻的i-1和i+1号同学是同类(i-1和i+1类型相同),他将回答"o",否则回答"x"。
      扮演农夫的同学总是说真话,即与他相邻的两个同学是同类,就回答“o”,不是同类就回答"x"
      扮演狼人的同学总是说假话,即与他相邻的两个同学是同类,就回答“x”,不是同类就回答"o"

      何老板从1到N位置依次询问了每个同学,根据同学们的答案,他是否能推断出每个人的身份呢?能输出每个人的身份:“S”代表农夫,“W”代表狼人,不能输出"-1"

    Input Format

    第一行,一个整数N
    第二行,一个长度为N且由字母x和o构成的字符串,依次表示1到N位置每个同学的回答。

    Output Format

    有解输出一行,一个长度为N的且由字母S和W构成的字符串,依次表示1到N位置每个同学的身份。如果有多解,输出字典序最小的一个。
    无解输出-1

    Sample Input 1

    6
    ooxoox

    Sample Output 1

    SSSWWS

    样例解释:
    合法的方案有多种SSSWWS、WSWSWW......

    Sample Input 2

    3
    oox

    Sample Output 2

    -1

    Sample Input 3

    10
    oxooxoxoox

    Sample Output 3

    SSWWSSSWWS

    Hint

    $3≤N≤10^5$