CSES - NOI 2019 - Results
Submission details
Task:Thieves and Prisons
Sender:Filip Björnåsen
Submission time:2019-03-06 15:16:36 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
Test results
testverdicttimegroup
#1ACCEPTED0.02 s2, 4, 5details
#2ACCEPTED0.02 s2, 4, 5details
#3ACCEPTED0.01 s2, 4, 5details
#4ACCEPTED0.02 s2, 4, 5details
#5ACCEPTED0.01 s2, 4, 5details
#6ACCEPTED0.02 s4, 5details
#7ACCEPTED0.02 s4, 5details
#8ACCEPTED0.01 s4, 5details
#9ACCEPTED0.02 s1, 3, 4, 5details
#100.02 s1, 3, 4, 5details
#110.02 s1, 3, 4, 5details
#12ACCEPTED0.01 s1, 3, 4, 5details
#130.02 s1, 3, 4, 5details
#140.02 s1, 3, 4, 5details
#15ACCEPTED0.02 s1, 3, 4, 5details
#16ACCEPTED0.01 s1, 3, 4, 5details
#17ACCEPTED0.01 s1, 2, 3, 4, 5details
#180.02 s1, 3, 4, 5details
#190.10 s2, 5details
#20ACCEPTED0.11 s2, 5details
#210.10 s2, 5details
#220.09 s5details
#23ACCEPTED0.09 s5details
#240.02 s3, 4, 5details
#250.02 s3, 4, 5details
#260.02 s3, 4, 5details
#270.02 s3, 4, 5details
#280.02 s4, 5details
#290.02 s4, 5details
#300.03 s4, 5details
#310.01 s4, 5details
#320.02 s2, 4, 5details
#330.01 s2, 4, 5details
#340.03 s2, 4, 5details
#350.02 s2, 4, 5details
#360.11 s3, 5details
#370.10 s3, 5details
#380.13 s3, 5details
#390.12 s3, 5details
#400.10 s5details
#410.11 s5details
#420.10 s5details
#430.11 s5details
#440.10 s2, 5details
#450.11 s2, 5details
#460.12 s2, 5details
#470.12 s2, 5details

Compiler report

input/code.cpp:5:0: warning: ignoring #pragma region Libraries [-Wunknown-pragmas]
 #pragma region Libraries
 
input/code.cpp:21:0: warning: ignoring #pragma endregion  [-Wunknown-pragmas]
 #pragma endregion

Code

using namespace std;
#pragma region Libraries
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <cstring>
#include <iomanip>
#pragma endregion
#define MP make_pair
#define all(v) v.begin(), v.end()
#define trav(it,v) for (auto it = v.begin(); it != v.end(); it++)
#define rep(index, from, to) for (int index = from; index < to; index++)
#define ll long long
#define pi pair<int,int>
int32_t main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n, k, m;
cin >> n >> k >> m;
vector<pair<char, int>> mo(m);
vector<stack<int>> ca(n, stack<int>());
for (int i = 0; i < m; i++)
{
cin >> mo[i].first >> mo[i].second;
mo[i].second--;
if (mo[i].first == 'C') {
ca[mo[i].second].push(i);
}
}
priority_queue<pair<int, int>> pq;
for (int i = 0; i < n; i++)
{
if (ca[i].size()) {
pq.push(MP(ca[i].top(), i));
ca[i].pop();
}
}
reverse(all(mo));
vector<int> ans(m);
unordered_set<int> avapri;
for (int i = 0; i < k; i++)
{
avapri.insert(i + 1);
}
int prev = 1;
for (int i = 0; i < m; i++)
{
if (mo[i].first == 'O') {
if (avapri.size() == 0) {
cout << "IMPOSSIBLE" << endl;
return 0;
}
int pri = *avapri.begin();
avapri.erase(pri);
while (pq.size() && (pq.top().first > i || ans[m - pq.top().first - 1] != 0)) {
pair<int, int> p = pq.top();
pq.pop();
if (ca[p.second].size() > 0) {
pq.push(MP(ca[p.second].top(), p.second));
ca[p.second].pop();
}
}
if (pq.size() == 0 || (pq.size() == 1 && pq.top().second == mo[i].second)) {
cout << "IMPOSSIBLE" << endl;
return 0;
}
else if (pq.size() == 1 || mo[i].second != pq.top().second) {
pair<int, int> p = pq.top();
pq.pop();
ans[n - i - p.first] = pri;
ans[i] = pri;
if (ca[p.second].size() > 0) {
pq.push(MP(ca[p.second].top(), p.second));
ca[p.second].pop();
}
}
else {
if (pq.top().second == mo[i].second) {
pair<int, int> temp = pq.top();
pq.pop();
pair<int, int> p = pq.top();
pq.pop();
ans[m - p.first - 1] = pri;
ans[i] = pri;
if (ca[p.second].size() > 0) {
pq.push(MP(ca[p.second].top(), p.second));
ca[p.second].pop();
}
pq.push(temp);
}
}
prev = pri;
}
else {
if (ans[i] != 0) {
avapri.insert(ans[i]);
continue;
}
ans[i] = prev;
}
}
reverse(all(ans));
reverse(all(mo));
vector<vector<int>> prison(k + 1, vector<int>());
vector<bool> inpri(n);
for (int i = 0; i < m; i++)
{
if (inpri[mo[i].second]) {
cout << "IMPOSSIBLE" << endl;
return 0;
}
if (mo[i].first == 'O') {
if (prison[ans[i]].size() == 0) {
cout << "IMPOSSIBLE" << endl;
return 0;
}
trav(it, prison[ans[i]]) {
inpri[*it] = 0;
}
prison[ans[i]].clear();
}
else {
prison[ans[i]].push_back(mo[i].second);
inpri[mo[i].second] = 1;
}
}
for (int i = 0; i < m; i++)
{
cout << ans[i] << " ";
}
#ifdef _DEBUG
system("pause");
#endif // _DEBUG
return 0;
}

Test details

Test 1

Group: 2, 4, 5

Verdict: ACCEPTED

input
1 1 1
C 1

correct output

user output

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

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

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
2 2 2 1 2 

Test 10

Group: 1, 3, 4, 5

Verdict:

input
3 2 5
C 1
C 2
O 3
O 3
...

correct output
2 1 2 1 1 

user output
IMPOSSIBLE

Test 11

Group: 1, 3, 4, 5

Verdict:

input
3 2 5
C 1
C 2
O 3
O 1
...

correct output
2 1 2 1 1 

user output
IMPOSSIBLE

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

Test 13

Group: 1, 3, 4, 5

Verdict:

input
3 2 4
C 1
O 2
C 1
O 3

correct output
1 1 1 1 

user output
IMPOSSIBLE

Test 14

Group: 1, 3, 4, 5

Verdict:

input
3 2 4
C 1
O 2
C 2
O 1

correct output
1 1 1 1 

user output
IMPOSSIBLE

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:

input
4 2 5
C 2
O 3
C 1
O 4
...

correct output
1 1 1 1 1 

user output
IMPOSSIBLE

Test 19

Group: 2, 5

Verdict:

input
100000 100000 100000
C 1
C 2
C 3
C 4
...

correct output
50000 49999 49998 49997 49996 ...

user output
IMPOSSIBLE

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
100000 100000 100000 100000 10...
Truncated

Test 21

Group: 2, 5

Verdict:

input
100000 100000 100000
C 1
C 2
C 3
C 4
...

correct output
20000 20000 20000 20000 20000 ...

user output
IMPOSSIBLE

Test 22

Group: 5

Verdict:

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
IMPOSSIBLE

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:

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:

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:

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:

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:

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
IMPOSSIBLE

Test 29

Group: 4, 5

Verdict:

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
IMPOSSIBLE

Test 30

Group: 4, 5

Verdict:

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
IMPOSSIBLE

Test 31

Group: 4, 5

Verdict:

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
IMPOSSIBLE

Test 32

Group: 2, 4, 5

Verdict:

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
IMPOSSIBLE

Test 33

Group: 2, 4, 5

Verdict:

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
IMPOSSIBLE

Test 34

Group: 2, 4, 5

Verdict:

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
IMPOSSIBLE

Test 35

Group: 2, 4, 5

Verdict:

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
IMPOSSIBLE

Test 36

Group: 3, 5

Verdict:

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:

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:

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:

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:

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
IMPOSSIBLE

Test 41

Group: 5

Verdict:

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
IMPOSSIBLE

Test 42

Group: 5

Verdict:

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
IMPOSSIBLE

Test 43

Group: 5

Verdict:

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
IMPOSSIBLE

Test 44

Group: 2, 5

Verdict:

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
IMPOSSIBLE

Test 45

Group: 2, 5

Verdict:

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
IMPOSSIBLE

Test 46

Group: 2, 5

Verdict:

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
IMPOSSIBLE

Test 47

Group: 2, 5

Verdict:

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
IMPOSSIBLE