Submission #1495179
Source Code Expand
#include <assert.h> #include <cstdint> #include <iostream> using namespace std; #define MAX_ANIMALS 100000 char animals[MAX_ANIMALS]; char answers[MAX_ANIMALS]; void decide_animals(uint64_t N) { for (uint64_t i = 1; i < N - 1; i++) { switch (animals[i]) { case 'S': if (answers[i] == 'o') { animals[i + 1] = animals[i - 1]; } else { animals[i + 1] = animals[i - 1] == 'S' ? 'W' : 'S'; } break; case 'W': if (answers[i] == 'x') { animals[i + 1] = animals[i - 1]; } else { animals[i + 1] = animals[i - 1] == 'S' ? 'W' : 'S'; } break; default: assert(0); break; } } } bool is_valid_at(uint64_t N, uint64_t at) { uint64_t pre = at - 1; if (at == 0) { pre = N - 1; } switch (animals[at]) { case 'S': if (answers[at] == 'o') { return animals[pre] == animals[(at + 1) % N]; } else { return animals[pre] != animals[(at + 1) % N]; } break; case 'W': if (answers[at] == 'x') { return animals[pre] == animals[(at + 1) % N]; } else { return animals[pre] != animals[(at + 1) % N]; } break; default: assert(0); break; } assert(0); return false; } bool check_validity(uint64_t N) { if (is_valid_at(N, 0) && is_valid_at(N, N - 1)) { return true; } return false; } void valid(uint64_t N) { for (uint64_t i = 0; i < N; i++) { cout << animals[i]; } cout << endl; } void invalid() { cout << -1 << endl; } int32_t main() { uint64_t N; cin >> N; for (uint64_t i = 0; i < N; i++) { char answer; cin >> answer; answers[i] = answer; } animals[0] = 'S'; animals[1] = 'S'; decide_animals(N); if (check_validity(N)) { valid(N); return 0; } animals[0] = 'S'; animals[1] = 'W'; decide_animals(N); if (check_validity(N)) { valid(N); return 0; } animals[0] = 'W'; animals[1] = 'S'; decide_animals(N); if (check_validity(N)) { valid(N); return 0; } animals[0] = 'W'; animals[1] = 'W'; decide_animals(N); if (check_validity(N)) { valid(N); return 0; } invalid(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Menagerie |
User | mohei |
Language | C++14 (GCC 5.4.1) |
Score | 500 |
Code Size | 2314 Byte |
Status | AC |
Exec Time | 12 ms |
Memory | 512 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 | 1 ms | 256 KB |
00_example_02.txt | AC | 1 ms | 256 KB |
00_example_03.txt | AC | 1 ms | 256 KB |
01.txt | AC | 8 ms | 384 KB |
02.txt | AC | 5 ms | 384 KB |
03.txt | AC | 1 ms | 256 KB |
04.txt | AC | 1 ms | 256 KB |
05.txt | AC | 10 ms | 512 KB |
06.txt | AC | 9 ms | 512 KB |
07.txt | AC | 3 ms | 256 KB |
08.txt | AC | 3 ms | 256 KB |
09.txt | AC | 2 ms | 256 KB |
10.txt | AC | 3 ms | 256 KB |
11.txt | AC | 12 ms | 512 KB |
12.txt | AC | 12 ms | 512 KB |
13.txt | AC | 11 ms | 512 KB |