Submission #1116396


Source Code Expand

Copy
#include<bits/stdc++.h>

using namespace std;


int N;
string S;

void rec(int idx1, bool t1, int idx2, bool t2, int idx, bool t3)
{
  vector< int > v(N, -1);
  v[idx] = t3;
  v[idx1] = t1;
  v[idx2] = t2;

  queue< int > que;
  que.push(idx1);
  que.push(idx2);

  while(!que.empty()) {
    int p = que.front();
    que.pop();
    int s = (p - 1 + N) % N;
    int t = (p + 1) % N;
    if(v[p]) {  // 真実
      if(S[p] == 'o') {
        if(~v[s] && ~v[t]) {
          if(v[s] != v[t]) return;
          continue;
        }
        if(~v[s]) v[t] = v[s], que.push(t);
        else v[s] = v[t], que.push(s);
      } else if(S[p] == 'x') {
        if(~v[s] && ~v[t]) {
          if(v[s] == v[t]) return;
          continue;
        }
        if(~v[s]) v[t] = v[s] ^ 1, que.push(t);
        else v[s] = v[t] ^ 1, que.push(s);
      }
    } else { // 逆
      if(S[p] == 'o') {
        if(~v[s] && ~v[t]) {
          if(v[s] == v[t]) return;
          continue;
        }
        if(~v[s]) v[t] = v[s] ^ 1, que.push(t);
        else v[s] = v[t] ^ 1, que.push(s);
      } else if(S[p] == 'x') {
        if(~v[s] && ~v[t]) {
          if(v[s] != v[t]) return;
          continue;
        }
        if(~v[s]) v[t] = v[s], que.push(t);
        else v[s] = v[t], que.push(s);
      }
    }
  }

  for(int i = 0; i < N; i++) {
    if(v[i]) cout << "S";
    else cout << "W";
  }
  cout << endl;
  exit(0);
}

int main()
{
  cin >> N;
  cin >> S;

  if(count(begin(S), end(S), 'o') == N) {
    cout << string(N, 'S') << endl;
    return (0);
  }

  for(int i = 0; i < S.size(); i++) {
    if(S[i] == 'x') {
      for(int j = 0; j < 2; j++) {
        for(int k = 0; k < 2; k++) {
          rec((i + N - 1) % N, j, (i + 1) % N, k, i, j != k);
        }
      }
      break;
    }
  }


  cout << -1 << endl;
}

Submission Info

Submission Time
Task D - Menagerie
User ei13333
Language C++14 (GCC 5.4.1)
Score 500
Code Size 1889 Byte
Status
Exec Time 15 ms
Memory 1016 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
All 500 / 500 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt
Case Name Status Exec Time Memory
00_example_01.txt 1 ms 256 KB
00_example_02.txt 1 ms 256 KB
00_example_03.txt 1 ms 256 KB
01.txt 10 ms 644 KB
02.txt 5 ms 640 KB
03.txt 1 ms 256 KB
04.txt 1 ms 256 KB
05.txt 13 ms 924 KB
06.txt 12 ms 928 KB
07.txt 3 ms 384 KB
08.txt 3 ms 384 KB
09.txt 2 ms 256 KB
10.txt 3 ms 384 KB
11.txt 11 ms 1016 KB
12.txt 11 ms 1016 KB
13.txt 15 ms 1016 KB