Submission #1120006
Source Code Expand
#include <iostream> #include <sstream> #include <algorithm> #include <functional> #include <iterator> #include <bitset> #include <string> #include <list> #include <vector> #include <stack> #include <queue> #include <set> #include <map> typedef signed long long int slli; typedef unsigned long long int ulli; const slli MAX_SLLI = 0x7FFFFFFFFFFFFFFF; const slli MIN_SLLI = 0x8000000000000000; const ulli MAX_ULLI = 0xFFFFFFFFFFFFFFFF; const ulli MIN_ULLI = 0x0000000000000000; #define N_TIMES(i, n) for (ulli i = 0; i < n; ++i) #define N_TIMES_REV(i, n) for (slli i = n - 1; i >= 0; --i) #ifdef __DEBUG__ template<typename T> std::ostream& operator<<(std::ostream &os, const std::list<T> &list) { const std::string delim = ", "; typename std::list<T>::const_iterator itr = list.begin(); while (itr != list.end()) { os << *itr; ++itr; if(itr != list.end()) os << delim; } return os; } template<typename T> std::ostream& operator<<(std::ostream &os, const std::vector<T> &v) { const std::string delim = ", "; for (unsigned n = 0; n < v.size(); ++n) { os << v[n]; if((n + 1) < v.size()) os << delim; } return os; } #endif const unsigned BITS_WIDTH = 1e+5 + 10; typedef std::bitset<BITS_WIDTH> Animals; #ifdef __DEBUG__ std::ostream& operator<<(std::ostream &os, const Animals &a) { os << a.to_string(); return os; } #endif bool search(unsigned N, const std::string &s, Animals &result) { std::vector<Animals> dp[2]; dp[0] = std::vector<Animals>(); dp[1] = std::vector<Animals>(); N_TIMES(i, 4) { dp[0].emplace_back(i); } for (unsigned n = 1; n <= N; ++n) { for (const Animals &a : dp[(n - 1) % 2]) { Animals b(a); if (s[n - 1] == 'o') { b[n + 1] = a[n] ? a[n - 1] : !a[n - 1]; } else { b[n + 1] = a[n] ? !a[n - 1] : a[n - 1]; } dp[n % 2].push_back(b); } if ((n + 1) <= N) dp[(n - 1) % 2].clear(); } for (const Animals &a : dp[N % 2]) { if ((a[0] == a[N + 0]) && (a[1] == a[N + 1])) { result = Animals(a); return true; } } return false; } int main() { unsigned N; std::cin >> N; std::string s; std::cin >> s; Animals a; if (!search(N, s, a)) { std::cout << -1 << std::endl; } else { for (unsigned n = 1; n <= N; ++n) { std::cout << (a[n] ? 'S' : 'W'); } std::cout << std::endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Menagerie |
User | material |
Language | C++14 (GCC 5.4.1) |
Score | 500 |
Code Size | 2531 Byte |
Status | AC |
Exec Time | 319 ms |
Memory | 640 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 500 / 500 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt |
All | 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 | AC | 2 ms | 512 KB |
00_example_02.txt | AC | 1 ms | 384 KB |
00_example_03.txt | AC | 1 ms | 384 KB |
01.txt | AC | 215 ms | 512 KB |
02.txt | AC | 147 ms | 512 KB |
03.txt | AC | 9 ms | 384 KB |
04.txt | AC | 1 ms | 384 KB |
05.txt | AC | 288 ms | 640 KB |
06.txt | AC | 285 ms | 640 KB |
07.txt | AC | 49 ms | 384 KB |
08.txt | AC | 57 ms | 512 KB |
09.txt | AC | 14 ms | 384 KB |
10.txt | AC | 62 ms | 384 KB |
11.txt | AC | 319 ms | 640 KB |
12.txt | AC | 317 ms | 640 KB |
13.txt | AC | 318 ms | 640 KB |