Task: | Thieves and Prisons |
Sender: | Mateusz Drwal |
Submission time: | 2019-03-06 15:09:19 +0200 |
Language: | C++ |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | WRONG ANSWER | 0 |
#2 | WRONG ANSWER | 0 |
#3 | WRONG ANSWER | 0 |
#4 | WRONG ANSWER | 0 |
#5 | WRONG ANSWER | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.03 s | 2, 4, 5 | details |
#2 | WRONG ANSWER | 0.03 s | 2, 4, 5 | details |
#3 | WRONG ANSWER | 0.02 s | 2, 4, 5 | details |
#4 | WRONG ANSWER | 0.02 s | 2, 4, 5 | details |
#5 | WRONG ANSWER | 0.01 s | 2, 4, 5 | details |
#6 | ACCEPTED | 0.02 s | 4, 5 | details |
#7 | WRONG ANSWER | 0.02 s | 4, 5 | details |
#8 | ACCEPTED | 0.01 s | 4, 5 | details |
#9 | ACCEPTED | 0.02 s | 1, 3, 4, 5 | details |
#10 | ACCEPTED | 0.01 s | 1, 3, 4, 5 | details |
#11 | ACCEPTED | 0.01 s | 1, 3, 4, 5 | details |
#12 | WRONG ANSWER | 0.01 s | 1, 3, 4, 5 | details |
#13 | ACCEPTED | 0.02 s | 1, 3, 4, 5 | details |
#14 | ACCEPTED | 0.02 s | 1, 3, 4, 5 | details |
#15 | ACCEPTED | 0.02 s | 1, 3, 4, 5 | details |
#16 | WRONG ANSWER | 0.02 s | 1, 3, 4, 5 | details |
#17 | WRONG ANSWER | 0.02 s | 1, 2, 3, 4, 5 | details |
#18 | ACCEPTED | 0.01 s | 1, 3, 4, 5 | details |
#19 | TIME LIMIT EXCEEDED | -- | 2, 5 | details |
#20 | ACCEPTED | 0.06 s | 2, 5 | details |
#21 | TIME LIMIT EXCEEDED | -- | 2, 5 | details |
#22 | WRONG ANSWER | 0.13 s | 5 | details |
#23 | WRONG ANSWER | 0.13 s | 5 | details |
#24 | ACCEPTED | 0.02 s | 3, 4, 5 | details |
#25 | ACCEPTED | 0.02 s | 3, 4, 5 | details |
#26 | ACCEPTED | 0.02 s | 3, 4, 5 | details |
#27 | ACCEPTED | 0.02 s | 3, 4, 5 | details |
#28 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
#29 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
#30 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
#31 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
#32 | TIME LIMIT EXCEEDED | -- | 2, 4, 5 | details |
#33 | TIME LIMIT EXCEEDED | -- | 2, 4, 5 | details |
#34 | TIME LIMIT EXCEEDED | -- | 2, 4, 5 | details |
#35 | TIME LIMIT EXCEEDED | -- | 2, 4, 5 | details |
#36 | RUNTIME ERROR | 0.31 s | 3, 5 | details |
#37 | RUNTIME ERROR | 0.32 s | 3, 5 | details |
#38 | ACCEPTED | 0.27 s | 3, 5 | details |
#39 | ACCEPTED | 0.18 s | 3, 5 | details |
#40 | TIME LIMIT EXCEEDED | -- | 5 | details |
#41 | TIME LIMIT EXCEEDED | -- | 5 | details |
#42 | TIME LIMIT EXCEEDED | -- | 5 | details |
#43 | TIME LIMIT EXCEEDED | -- | 5 | details |
#44 | TIME LIMIT EXCEEDED | -- | 2, 5 | details |
#45 | TIME LIMIT EXCEEDED | -- | 2, 5 | details |
#46 | TIME LIMIT EXCEEDED | -- | 2, 5 | details |
#47 | TIME LIMIT EXCEEDED | -- | 2, 5 | details |
Compiler report
input/code.cpp: In function 'bool dfs(int)': input/code.cpp:37:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int j = 0; j < prisons[i].size(); j++) { ~~^~~~~~~~~~~~~~~~~~~
Code
#include <bits/stdc++.h>using namespace std;int n, k, m;vector<pair<bool, int>> events; // true: capture, false: releasevector<vector<int>> prisons;vector<int> answer;vector<bool> caught;bool dfs(int event) {if (event == m) {return true;}if (caught[events[event].second]) return false;if (events[event].first) {caught[events[event].second] = true;for (int i = 0; i < k; i++) {prisons[i].push_back(events[event].second);if (dfs(event+1)) {answer[event] = i+1;return true;}prisons[i].pop_back();}} else {for (int i = 0; i < k; i++) {if (prisons[i].size() == 0) continue;auto tmpPrisons = prisons[i];auto tmpCaught = caught;for (int j = 0; j < prisons[i].size(); j++) {caught[prisons[i][j]] = false;}prisons[i].clear();if (dfs(event+1)) {answer[event] = i+1;return true;}prisons[i] = tmpPrisons;caught = tmpCaught;}}return false;}int main() {cin.sync_with_stdio(false);cin.tie(0);cin >> n >> k >> m;events.resize(m);prisons.resize(k);answer.resize(m);caught.resize(n, false);char type;for (int i = 0; i < m; i++) {cin >> type >> events[i].second;events[i].second--;events[i].first = type == 'C';}dfs(0);for (int prison : answer) {cout << prison << " ";}return 0;}
Test details
Test 1
Group: 2, 4, 5
Verdict: ACCEPTED
input |
---|
1 1 1 C 1 |
correct output |
---|
1 |
user output |
---|
1 |
Test 2
Group: 2, 4, 5
Verdict: WRONG ANSWER
input |
---|
1 1 1 O 1 |
correct output |
---|
IMPOSSIBLE |
user output |
---|
0 |
Test 3
Group: 2, 4, 5
Verdict: WRONG ANSWER
input |
---|
1 1 2 C 1 C 1 |
correct output |
---|
IMPOSSIBLE |
user output |
---|
0 0 |
Test 4
Group: 2, 4, 5
Verdict: WRONG ANSWER
input |
---|
1 1 2 C 1 O 1 |
correct output |
---|
IMPOSSIBLE |
user output |
---|
0 0 |
Test 5
Group: 2, 4, 5
Verdict: WRONG ANSWER
input |
---|
1 1 2 O 1 C 1 |
correct output |
---|
IMPOSSIBLE |
user output |
---|
0 0 |
Test 6
Group: 4, 5
Verdict: ACCEPTED
input |
---|
2 1 2 C 1 C 2 |
correct output |
---|
1 1 |
user output |
---|
1 1 |
Test 7
Group: 4, 5
Verdict: WRONG ANSWER
input |
---|
2 1 2 C 1 O 1 |
correct output |
---|
IMPOSSIBLE |
user output |
---|
0 0 |
Test 8
Group: 4, 5
Verdict: ACCEPTED
input |
---|
2 1 2 C 1 O 2 |
correct output |
---|
1 1 |
user output |
---|
1 1 |
Test 9
Group: 1, 3, 4, 5
Verdict: ACCEPTED
input |
---|
3 2 5 C 1 C 2 O 3 C 1 ... |
correct output |
---|
1 1 1 1 1 |
user output |
---|
1 1 1 1 1 |
Test 10
Group: 1, 3, 4, 5
Verdict: ACCEPTED
input |
---|
3 2 5 C 1 C 2 O 3 O 3 ... |
correct output |
---|
2 1 2 1 1 |
user output |
---|
1 2 1 2 1 |
Test 11
Group: 1, 3, 4, 5
Verdict: ACCEPTED
input |
---|
3 2 5 C 1 C 2 O 3 O 1 ... |
correct output |
---|
2 1 2 1 1 |
user output |
---|
1 2 1 2 1 |
Test 12
Group: 1, 3, 4, 5
Verdict: WRONG ANSWER
input |
---|
3 2 5 C 1 C 2 O 1 O 3 ... |
correct output |
---|
IMPOSSIBLE |
user output |
---|
0 0 0 0 0 |
Test 13
Group: 1, 3, 4, 5
Verdict: ACCEPTED
input |
---|
3 2 4 C 1 O 2 C 1 O 3 |
correct output |
---|
1 1 1 1 |
user output |
---|
1 1 1 1 |
Test 14
Group: 1, 3, 4, 5
Verdict: ACCEPTED
input |
---|
3 2 4 C 1 O 2 C 2 O 1 |
correct output |
---|
1 1 1 1 |
user output |
---|
1 1 1 1 |
Test 15
Group: 1, 3, 4, 5
Verdict: ACCEPTED
input |
---|
3 2 3 C 1 C 2 C 3 |
correct output |
---|
1 1 1 |
user output |
---|
1 1 1 |
Test 16
Group: 1, 3, 4, 5
Verdict: WRONG ANSWER
input |
---|
3 2 3 O 1 C 2 C 3 |
correct output |
---|
IMPOSSIBLE |
user output |
---|
0 0 0 |
Test 17
Group: 1, 2, 3, 4, 5
Verdict: WRONG ANSWER
input |
---|
2 2 7 C 1 O 2 O 2 O 2 ... |
correct output |
---|
IMPOSSIBLE |
user output |
---|
0 0 0 0 0 0 0 |
Test 18
Group: 1, 3, 4, 5
Verdict: ACCEPTED
input |
---|
4 2 5 C 2 O 3 C 1 O 4 ... |
correct output |
---|
1 1 1 1 1 |
user output |
---|
1 1 1 1 1 |
Test 19
Group: 2, 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 100000 100000 C 1 C 2 C 3 C 4 ... |
correct output |
---|
50000 49999 49998 49997 49996 ... |
user output |
---|
(empty) |
Test 20
Group: 2, 5
Verdict: ACCEPTED
input |
---|
100000 100000 100000 C 1 C 2 C 3 C 4 ... |
correct output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
user output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... Truncated |
Test 21
Group: 2, 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 100000 100000 C 1 C 2 C 3 C 4 ... |
correct output |
---|
20000 20000 20000 20000 20000 ... |
user output |
---|
(empty) |
Test 22
Group: 5
Verdict: WRONG ANSWER
input |
---|
100000 100 100000 C 1 C 2 C 3 C 4 ... |
correct output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
user output |
---|
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... Truncated |
Test 23
Group: 5
Verdict: WRONG ANSWER
input |
---|
100000 99 100000 C 1 C 2 C 3 C 4 ... |
correct output |
---|
IMPOSSIBLE |
user output |
---|
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... Truncated |
Test 24
Group: 3, 4, 5
Verdict: ACCEPTED
input |
---|
500 2 500 C 384 O 62 C 387 O 473 ... |
correct output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
user output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... Truncated |
Test 25
Group: 3, 4, 5
Verdict: ACCEPTED
input |
---|
500 2 500 C 384 O 62 C 387 O 473 ... |
correct output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 ... |
user output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 ... Truncated |
Test 26
Group: 3, 4, 5
Verdict: ACCEPTED
input |
---|
500 2 500 C 384 O 62 C 387 O 473 ... |
correct output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 ... |
user output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 ... Truncated |
Test 27
Group: 3, 4, 5
Verdict: ACCEPTED
input |
---|
500 2 500 C 384 O 62 C 387 C 473 ... |
correct output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
user output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... Truncated |
Test 28
Group: 4, 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 250 500 C 384 O 62 C 387 O 473 ... |
correct output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
user output |
---|
(empty) |
Test 29
Group: 4, 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 250 500 C 384 O 62 C 387 O 473 ... |
correct output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 2 1 3 ... |
user output |
---|
(empty) |
Test 30
Group: 4, 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 250 500 C 384 O 62 C 387 O 473 ... |
correct output |
---|
1 1 1 1 1 3 2 3 3 2 2 2 5 4 2 ... |
user output |
---|
(empty) |
Test 31
Group: 4, 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 250 500 C 384 O 62 C 387 C 473 ... |
correct output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
user output |
---|
(empty) |
Test 32
Group: 2, 4, 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 500 C 384 O 62 C 387 O 473 ... |
correct output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
user output |
---|
(empty) |
Test 33
Group: 2, 4, 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 500 C 384 O 62 C 387 O 473 ... |
correct output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 2 1 3 ... |
user output |
---|
(empty) |
Test 34
Group: 2, 4, 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 500 C 384 O 62 C 387 O 473 ... |
correct output |
---|
1 1 1 1 2 1 3 3 3 2 2 2 2 4 5 ... |
user output |
---|
(empty) |
Test 35
Group: 2, 4, 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 500 C 384 O 62 C 387 C 473 ... |
correct output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
user output |
---|
(empty) |
Test 36
Group: 3, 5
Verdict: RUNTIME ERROR
input |
---|
100000 2 100000 C 89384 O 54062 C 85387 O 53318 ... |
correct output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
user output |
---|
(empty) |
Test 37
Group: 3, 5
Verdict: RUNTIME ERROR
input |
---|
100000 2 100000 C 89384 O 54062 C 85387 O 53318 ... |
correct output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 ... |
user output |
---|
(empty) |
Test 38
Group: 3, 5
Verdict: ACCEPTED
input |
---|
100000 2 100000 C 89384 O 54062 C 85387 O 53318 ... |
correct output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 ... |
user output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 ... Truncated |
Test 39
Group: 3, 5
Verdict: ACCEPTED
input |
---|
100000 2 100000 C 89384 O 54062 C 85387 C 53318 ... |
correct output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
user output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... Truncated |
Test 40
Group: 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 50000 100000 C 89384 O 54062 C 85387 O 53318 ... |
correct output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
user output |
---|
(empty) |
Test 41
Group: 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 50000 100000 C 89384 O 54062 C 85387 O 53318 ... |
correct output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 ... |
user output |
---|
(empty) |
Test 42
Group: 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 50000 100000 C 89384 O 54062 C 85387 O 53318 ... |
correct output |
---|
1 1 1 1 1 3 2 3 3 3 3 3 3 4 5 ... |
user output |
---|
(empty) |
Test 43
Group: 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 50000 100000 C 89384 O 54062 C 85387 C 53318 ... |
correct output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
user output |
---|
(empty) |
Test 44
Group: 2, 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 100000 100000 C 89384 O 54062 C 85387 O 53318 ... |
correct output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
user output |
---|
(empty) |
Test 45
Group: 2, 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 100000 100000 C 89384 O 54062 C 85387 O 53318 ... |
correct output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 ... |
user output |
---|
(empty) |
Test 46
Group: 2, 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 100000 100000 C 89384 O 54062 C 85387 O 53318 ... |
correct output |
---|
1 1 1 1 2 1 3 3 3 3 3 3 4 5 3 ... |
user output |
---|
(empty) |
Test 47
Group: 2, 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 100000 100000 C 89384 O 54062 C 85387 C 53318 ... |
correct output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
user output |
---|
(empty) |