Task: | Sulut |
Sender: | Bean Benestrom |
Submission time: | 2024-01-20 16:42:48 +0200 |
Language: | C++17 |
Status: | READY |
Result: | 12 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 12 |
#2 | TIME LIMIT EXCEEDED | 0 |
#3 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.00 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.00 s | 1, 2, 3 | details |
#3 | ACCEPTED | 0.00 s | 1, 2, 3 | details |
#4 | ACCEPTED | 0.00 s | 1, 2, 3 | details |
#5 | ACCEPTED | 0.00 s | 1, 2, 3 | details |
#6 | ACCEPTED | 0.00 s | 1, 2, 3 | details |
#7 | ACCEPTED | 0.00 s | 1, 2, 3 | details |
#8 | ACCEPTED | 0.00 s | 1, 2, 3 | details |
#9 | ACCEPTED | 0.00 s | 1, 2, 3 | details |
#10 | ACCEPTED | 0.00 s | 1, 2, 3 | details |
#11 | ACCEPTED | 0.00 s | 1, 2, 3 | details |
#12 | ACCEPTED | 0.00 s | 1, 2, 3 | details |
#13 | ACCEPTED | 0.00 s | 1, 2, 3 | details |
#14 | ACCEPTED | 0.00 s | 1, 2, 3 | details |
#15 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#16 | ACCEPTED | 0.00 s | 1, 2, 3 | details |
#17 | ACCEPTED | 0.00 s | 1, 2, 3 | details |
#18 | ACCEPTED | 0.00 s | 1, 2, 3 | details |
#19 | ACCEPTED | 0.00 s | 1, 2, 3 | details |
#20 | ACCEPTED | 0.00 s | 2, 3 | details |
#21 | TIME LIMIT EXCEEDED | -- | 2, 3 | details |
#22 | TIME LIMIT EXCEEDED | -- | 2, 3 | details |
#23 | TIME LIMIT EXCEEDED | -- | 2, 3 | details |
#24 | TIME LIMIT EXCEEDED | -- | 2, 3 | details |
#25 | RUNTIME ERROR | 0.41 s | 3 | details |
#26 | RUNTIME ERROR | 0.42 s | 3 | details |
#27 | RUNTIME ERROR | 0.41 s | 3 | details |
#28 | RUNTIME ERROR | 0.41 s | 3 | details |
#29 | RUNTIME ERROR | 0.42 s | 3 | details |
Code
#include <iostream> #include <vector> #include <algorithm> #include <array> #include <unordered_map> int SIZE, DIFF; std::vector<bool> solutionA; std::vector<bool> solutionB; std::string A; std::string B; std::string get_as_string(const std::vector<bool>& x) { std::string string; for (bool Q : x) { string += (Q ? '(' : ')'); } return string; } struct HASH { std::size_t operator()(const std::array<int, 4>& array) const { std::size_t h = 0; for (auto e : array) { h ^= std::hash<int>{}(e) + 0x9e3779b9 + (h << 6) + (h >> 2); } return h; } }; std::unordered_map<std::array<int, 4>, bool, HASH> map; // (openA, openB, size, difference) // 1 = '(' 0 = ')' bool solve(std::vector<bool> groupA, std::vector<bool> groupB, int openA, int openB, int difference, int size) { /* A = get_as_string(groupA); B = get_as_string(groupB); */ if (difference > DIFF) return false; if (openA < 0 || openA - (SIZE - size) > 0) return false; if (openB < 0 || openB - (SIZE - size) > 0) return false; if (size == SIZE) { if (difference != DIFF) return false; solutionA = groupA; solutionB = groupB; return true; } groupA.push_back(1); groupB.push_back(1); if (!map[{openA+1, openB+1, difference, size+1}]) { bool value = solve(groupA, groupB, openA+1, openB+1, difference, size+1); map[{openA+1, openB+1, difference, size+1}] = value; if (value) return true; } groupB[groupB.size()-1] = 0; if (!map[{openA+1, openB-1, difference+1, size+1}]) { bool value = solve(groupA, groupB, openA+1, openB-1, difference+1, size+1); map[{openA+1, openB-1, difference+1, size+1}] = value; if (value) return true; } groupA[groupA.size()-1] = 0; if (!map[{openA-1, openB-1, difference, size+1}]) { bool value = solve(groupA, groupB, openA-1, openB-1, difference, size+1); map[{openA-1, openB-1, difference, size+1}] = value; if (value) return true; } groupB[groupB.size()-1] = 1; if (!map[{openA-1, openB+1, difference+1, size+1}]) { bool value = solve(groupA, groupB, openA-1, openB+1, difference+1, size+1); map[{openA-1, openB+1, difference+1, size+1}] = value; if (value) return true; } return false; } int main() { std::cin >> SIZE >> DIFF; if (SIZE % 2 == 1 || DIFF % 2 == 1) { std::cout << "IMPOSSIBLE"; return 0; } solve({1}, {1}, 1, 1, 0, 1); std::string stringA; std::string stringB; if (!solutionA.size()) { std::cout << "IMPOSSIBLE"; return 0; } std::cout << get_as_string(solutionA) << '\n'; std::cout << get_as_string(solutionB) << '\n'; /* if (DIFF > SIZE/2) { std::cout << "IMPOSSIBLE"; return 0; } */ return 0; } /* ACCEABFFZZZZ */
Test details
Test 1
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
2 0 |
correct output |
---|
() () |
user output |
---|
() () |
Test 2
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
4 0 |
correct output |
---|
()() ()() |
user output |
---|
(()) (()) |
Test 3
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
4 2 |
correct output |
---|
()() (()) |
user output |
---|
(()) ()() |
Test 4
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
6 0 |
correct output |
---|
()()() ()()() |
user output |
---|
((())) ((())) |
Test 5
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
6 2 |
correct output |
---|
()()() ()(()) |
user output |
---|
((())) (())() |
Test 6
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
6 4 |
correct output |
---|
()()() (()()) |
user output |
---|
(()()) ()()() |
Test 7
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
8 0 |
correct output |
---|
()()()() ()()()() |
user output |
---|
(((()))) (((()))) |
Test 8
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
8 2 |
correct output |
---|
()()()() ()()(()) |
user output |
---|
(((()))) ((()))() |
Test 9
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
8 4 |
correct output |
---|
()()()() ()(()()) |
user output |
---|
(((()))) (())()() |
Test 10
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
8 6 |
correct output |
---|
()()()() (()()()) |
user output |
---|
(()()()) ()()()() |
Test 11
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
10 0 |
correct output |
---|
()()()()() ()()()()() |
user output |
---|
((((())))) ((((())))) |
Test 12
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
10 2 |
correct output |
---|
()()()()() ()()()(()) |
user output |
---|
((((())))) (((())))() |
Test 13
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
10 4 |
correct output |
---|
()()()()() ()()(()()) |
user output |
---|
((((())))) ((()))()() |
Test 14
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
10 6 |
correct output |
---|
()()()()() ()(()()()) |
user output |
---|
(((()()))) (())()()() |
Test 15
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
10 8 |
correct output |
---|
()()()()() (()()()()) |
user output |
---|
(()()()()) ()()()()() |
Test 16
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
4 1 |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |
Test 17
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
4 4 |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |
Test 18
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
5 1 |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |
Test 19
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
5 2 |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |
Test 20
Group: 2, 3
Verdict: ACCEPTED
input |
---|
100 0 |
correct output |
---|
()()()()()()()()()()()()()()()... |
user output |
---|
((((((((((((((((((((((((((((((... Truncated |
Test 21
Group: 2, 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
100 10 |
correct output |
---|
()()()()()()()()()()()()()()()... |
user output |
---|
(empty) |
Test 22
Group: 2, 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
100 42 |
correct output |
---|
()()()()()()()()()()()()()()()... |
user output |
---|
(empty) |
Test 23
Group: 2, 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
100 80 |
correct output |
---|
()()()()()()()()()()()()()()()... |
user output |
---|
(empty) |
Test 24
Group: 2, 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
100 98 |
correct output |
---|
()()()()()()()()()()()()()()()... |
user output |
---|
(empty) |
Test 25
Group: 3
Verdict: RUNTIME ERROR
input |
---|
1000000 0 |
correct output |
---|
()()()()()()()()()()()()()()()... |
user output |
---|
(empty) |
Test 26
Group: 3
Verdict: RUNTIME ERROR
input |
---|
1000000 42 |
correct output |
---|
()()()()()()()()()()()()()()()... |
user output |
---|
(empty) |
Test 27
Group: 3
Verdict: RUNTIME ERROR
input |
---|
1000000 4242 |
correct output |
---|
()()()()()()()()()()()()()()()... |
user output |
---|
(empty) |
Test 28
Group: 3
Verdict: RUNTIME ERROR
input |
---|
1000000 424242 |
correct output |
---|
()()()()()()()()()()()()()()()... |
user output |
---|
(empty) |
Test 29
Group: 3
Verdict: RUNTIME ERROR
input |
---|
1000000 999998 |
correct output |
---|
()()()()()()()()()()()()()()()... |
user output |
---|
(empty) |