Task: | Thieves and Prisons |
Sender: | Olli Järviniemi |
Submission time: | 2019-03-06 13:19:54 +0200 |
Language: | C++ |
Status: | READY |
Result: | 21 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 8 |
#2 | ACCEPTED | 13 |
#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 | ACCEPTED | 0.03 s | 2, 4, 5 | details |
#3 | ACCEPTED | 0.03 s | 2, 4, 5 | details |
#4 | ACCEPTED | 0.02 s | 2, 4, 5 | details |
#5 | ACCEPTED | 0.03 s | 2, 4, 5 | details |
#6 | ACCEPTED | 0.04 s | 4, 5 | details |
#7 | ACCEPTED | 0.03 s | 4, 5 | details |
#8 | ACCEPTED | 0.02 s | 4, 5 | details |
#9 | ACCEPTED | 0.03 s | 1, 3, 4, 5 | details |
#10 | ACCEPTED | 0.03 s | 1, 3, 4, 5 | details |
#11 | ACCEPTED | 0.03 s | 1, 3, 4, 5 | details |
#12 | ACCEPTED | 0.03 s | 1, 3, 4, 5 | details |
#13 | ACCEPTED | 0.04 s | 1, 3, 4, 5 | details |
#14 | ACCEPTED | 0.03 s | 1, 3, 4, 5 | details |
#15 | ACCEPTED | 0.03 s | 1, 3, 4, 5 | details |
#16 | ACCEPTED | 0.03 s | 1, 3, 4, 5 | details |
#17 | ACCEPTED | 0.02 s | 1, 2, 3, 4, 5 | details |
#18 | ACCEPTED | 0.04 s | 1, 3, 4, 5 | details |
#19 | ACCEPTED | 0.17 s | 2, 5 | details |
#20 | ACCEPTED | 0.21 s | 2, 5 | details |
#21 | ACCEPTED | 0.20 s | 2, 5 | details |
#22 | ACCEPTED | 0.17 s | 5 | details |
#23 | ACCEPTED | 0.16 s | 5 | details |
#24 | WRONG ANSWER | 0.03 s | 3, 4, 5 | details |
#25 | WRONG ANSWER | 0.03 s | 3, 4, 5 | details |
#26 | WRONG ANSWER | 0.05 s | 3, 4, 5 | details |
#27 | WRONG ANSWER | 0.03 s | 3, 4, 5 | details |
#28 | ACCEPTED | 0.03 s | 4, 5 | details |
#29 | ACCEPTED | 0.02 s | 4, 5 | details |
#30 | ACCEPTED | 0.03 s | 4, 5 | details |
#31 | ACCEPTED | 0.03 s | 4, 5 | details |
#32 | ACCEPTED | 0.02 s | 2, 4, 5 | details |
#33 | ACCEPTED | 0.04 s | 2, 4, 5 | details |
#34 | ACCEPTED | 0.04 s | 2, 4, 5 | details |
#35 | ACCEPTED | 0.03 s | 2, 4, 5 | details |
#36 | WRONG ANSWER | 0.12 s | 3, 5 | details |
#37 | WRONG ANSWER | 0.12 s | 3, 5 | details |
#38 | WRONG ANSWER | 0.13 s | 3, 5 | details |
#39 | WRONG ANSWER | 0.13 s | 3, 5 | details |
#40 | ACCEPTED | 0.17 s | 5 | details |
#41 | ACCEPTED | 0.18 s | 5 | details |
#42 | ACCEPTED | 0.19 s | 5 | details |
#43 | ACCEPTED | 0.19 s | 5 | details |
#44 | ACCEPTED | 0.18 s | 2, 5 | details |
#45 | ACCEPTED | 0.19 s | 2, 5 | details |
#46 | ACCEPTED | 0.21 s | 2, 5 | details |
#47 | ACCEPTED | 0.19 s | 2, 5 | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:124:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int j = 0; j < del[i].size(); ++j) { ~~^~~~~~~~~~~~~~~ input/code.cpp:167:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int j = 0; j < cont[ans[i-1]].size(); ++j) { ~~^~~~~~~~~~~~~~~~~~~~~~~ input/code.cpp:180:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int i = 0; i < ans.size(); ++i) { ~~^~~~~~~~~~~~ input/code.cpp:190:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int j = 0; j < del[i].size(); ++j) { ~~^~~~~~~~~~~~~~~
Code
#include <iostream>#include <set>#include <vector>#include <algorithm>using namespace std;const int N = 1e5 + 5;typedef pair<int, int> pii;typedef long long ll;set<int> per[N];int pri[N];int mi[N];int w[N];vector<int> del[N];set<int> fre;vector<int> loc[N];bool impri[N];vector<int> cont[N];int main() {int n, k, m;cin >> n >> k >> m;vector<int> g;vector<char> t;g.push_back(-1);t.push_back(-1);for(int i = 1; i <= m; ++i) {char a; int b;cin >> a >> b;t.push_back(a);g.push_back(b);per[b].insert(i);if(b > n) {cout << "IMPOSSIBLE\n";return 0;}}if(t[1] == 'C') {pri[1] = 1;} else {cout << "IMPOSSIBLE\n";return 0;}for(int i = 2; i <= m; ++i) {if(t[i] == 'C') {pri[i] = pri[i-1] + 1;} else {pri[i] = pri[i-1] - 1;}}mi[m] = pri[m];for(int i = m-1; i >= 1; --i) {mi[i] = min(mi[i+1], pri[i]);}if(mi[1] < 0) {cout << "IMPOSSIBLE\n";return 0;}int ext = 0;int curPri = 0;for(int i = 1; i <= m; ++i) {if(t[i] == 'C') {++curPri;continue;}w[i] = min(mi[i] + 1 - ext, curPri);curPri -= w[i];ext += w[i] - 1;}set<pair<int, int> > ord;set<int> people;for(int i = 1; i <= m; ++i) {if(t[i] == 'C') {if(people.count(g[i]) > 0) {cout << "IMPOSSIBLE\n";return 0;}people.insert(g[i]);set<int>::iterator it = per[g[i]].upper_bound(i);if(it == per[g[i]].end()) {ord.insert({N, g[i]});} else {ord.insert({*(per[g[i]].upper_bound(i)), g[i]});}continue;}for(int j = 1; j <= w[i]; ++j) {auto it = ord.begin();del[i].push_back((*it).second);people.erase((*it).second);ord.erase(it);}}for(int i = 1; i <= k; ++i) {fre.insert(i);}for(int i = 1; i <= m; ++i) {if(t[i] == 'C') continue;if(fre.size() == 0) {cout << "IMPOSSIBLE\n";return 0;}int pr = *(fre.begin());fre.erase(fre.begin());for(int j = 0; j < del[i].size(); ++j) {int mm = del[i][j];loc[mm].push_back(pr);continue;}loc[g[i]].push_back(pr);}for(int i = 1; i <= m; ++i) {reverse(loc[i].begin(), loc[i].end());}/* for(int i = 1; i <= n; ++i) {cout << "The prisons for " << i << ": ";for(int j = 0; j < loc[i].size(); ++j) {cout << loc[i][j] << " ";}cout << "\n";}*/vector<int> ans;for(int i = 1; i <= m; ++i) {if(loc[g[i]].size() == 0) {ans.push_back(1);} else {ans.push_back(loc[g[i]][loc[g[i]].size() - 1]);loc[g[i]].pop_back();}if(t[i] == 'C') {cont[ans[i-1]].push_back(g[i]);if(impri[g[i]]) {cout << "IMPOSSIBLE\n";return 0;}impri[g[i]] = true;} else {if(impri[g[i]]) {cout << "IMPOSSIBLE\n";cout << "ere\n";cout << g[i] << "\n";return 0;}for(int j = 0; j < cont[ans[i-1]].size(); ++j) {int abb = cont[ans[i-1]][j];if(!impri[abb]) {cout << "IMPOSSIBLE\n";return 0;}impri[abb] = false;}cont[ans[i-1]].clear();}}for(int i = 0; i < ans.size(); ++i) {cout << ans[i] << " ";}cout << "\n";return 0;cout << "\n\n";for(int i = 1; i <= m; ++i) {cout << del[i].size() << ": ";for(int j = 0; j < del[i].size(); ++j) {cout << del[i][j] << " ";}cout << "\n";}}
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: ACCEPTED
input |
---|
1 1 1 O 1 |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |
Test 3
Group: 2, 4, 5
Verdict: ACCEPTED
input |
---|
1 1 2 C 1 C 1 |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |
Test 4
Group: 2, 4, 5
Verdict: ACCEPTED
input |
---|
1 1 2 C 1 O 1 |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE ere 1 |
Test 5
Group: 2, 4, 5
Verdict: ACCEPTED
input |
---|
1 1 2 O 1 C 1 |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |
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: ACCEPTED
input |
---|
2 1 2 C 1 O 1 |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE ere 1 |
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: ACCEPTED
input |
---|
3 2 5 C 1 C 2 O 1 O 3 ... |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE ere 1 |
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 2 2 |
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 2 2 |
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: ACCEPTED
input |
---|
3 2 3 O 1 C 2 C 3 |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |
Test 17
Group: 1, 2, 3, 4, 5
Verdict: ACCEPTED
input |
---|
2 2 7 C 1 O 2 O 2 O 2 ... |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |
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 2 2 1 |
Test 19
Group: 2, 5
Verdict: ACCEPTED
input |
---|
100000 100000 100000 C 1 C 2 C 3 C 4 ... |
correct output |
---|
50000 49999 49998 49997 49996 ... |
user output |
---|
1 2 3 4 5 6 7 8 9 10 11 12 13 ... Truncated |
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: ACCEPTED
input |
---|
100000 100000 100000 C 1 C 2 C 3 C 4 ... |
correct output |
---|
20000 20000 20000 20000 20000 ... |
user output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... Truncated |
Test 22
Group: 5
Verdict: ACCEPTED
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 |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... Truncated |
Test 23
Group: 5
Verdict: ACCEPTED
input |
---|
100000 99 100000 C 1 C 2 C 3 C 4 ... |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |
Test 24
Group: 3, 4, 5
Verdict: WRONG ANSWER
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 |
---|
IMPOSSIBLE |
Test 25
Group: 3, 4, 5
Verdict: WRONG ANSWER
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 |
---|
IMPOSSIBLE |
Test 26
Group: 3, 4, 5
Verdict: WRONG ANSWER
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 |
---|
IMPOSSIBLE |
Test 27
Group: 3, 4, 5
Verdict: WRONG ANSWER
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 |
---|
IMPOSSIBLE |
Test 28
Group: 4, 5
Verdict: ACCEPTED
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 |
---|
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 ... Truncated |
Test 29
Group: 4, 5
Verdict: ACCEPTED
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 |
---|
1 1 2 2 3 3 4 4 5 5 6 6 9 8 7 ... Truncated |
Test 30
Group: 4, 5
Verdict: ACCEPTED
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 |
---|
1 1 2 2 7 3 4 3 10 4 5 5 6 8 9... Truncated |
Test 31
Group: 4, 5
Verdict: ACCEPTED
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 |
---|
1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 ... Truncated |
Test 32
Group: 2, 4, 5
Verdict: ACCEPTED
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 |
---|
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 ... Truncated |
Test 33
Group: 2, 4, 5
Verdict: ACCEPTED
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 |
---|
1 1 2 2 3 3 4 4 5 5 6 6 8 9 7 ... Truncated |
Test 34
Group: 2, 4, 5
Verdict: ACCEPTED
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 |
---|
1 1 2 2 4 8 3 3 9 4 5 5 10 7 6... Truncated |
Test 35
Group: 2, 4, 5
Verdict: ACCEPTED
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 |
---|
1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 ... Truncated |
Test 36
Group: 3, 5
Verdict: WRONG ANSWER
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 |
---|
IMPOSSIBLE |
Test 37
Group: 3, 5
Verdict: WRONG ANSWER
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 |
---|
IMPOSSIBLE |
Test 38
Group: 3, 5
Verdict: WRONG ANSWER
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 |
---|
IMPOSSIBLE |
Test 39
Group: 3, 5
Verdict: WRONG ANSWER
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 |
---|
IMPOSSIBLE |
Test 40
Group: 5
Verdict: ACCEPTED
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 |
---|
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 ... Truncated |
Test 41
Group: 5
Verdict: ACCEPTED
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 |
---|
1 1 2 2 3 3 4 4 5 5 6 6 7 9 8 ... Truncated |
Test 42
Group: 5
Verdict: ACCEPTED
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 |
---|
1 1 2 2 9 3 8 3 4 4 5 5 10 7 6... Truncated |
Test 43
Group: 5
Verdict: ACCEPTED
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 |
---|
1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 ... Truncated |
Test 44
Group: 2, 5
Verdict: ACCEPTED
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 |
---|
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 ... Truncated |
Test 45
Group: 2, 5
Verdict: ACCEPTED
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 |
---|
1 1 2 2 3 3 4 4 5 5 6 6 7 8 9 ... Truncated |
Test 46
Group: 2, 5
Verdict: ACCEPTED
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 |
---|
1 1 2 2 8 9 3 3 4 4 5 5 7 6 10... Truncated |
Test 47
Group: 2, 5
Verdict: ACCEPTED
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 |
---|
1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 ... Truncated |