# NOI 2019 Open

 Start: N/A End: N/A

CSES - NOI 2019 Open - Results
History
After contest21
After contest13
After contest0
3:31:200
3:13:330
3:11:580
 Task: Thieves and Prisons Sender: jakob_nogler Submission time: 2019-03-11 19:29:16 Language: C++ Status: READY Score: 0

## Feedback

 group verdict score #1 WRONG ANSWER 0 #2 TIME LIMIT EXCEEDED 0 #3 WRONG ANSWER 0 #4 WRONG ANSWER 0 #5 WRONG ANSWER 0

## Compiler report

```input/code.cpp: In function 'int main()':
input/code.cpp:78:16: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
if(cnt = 0){
~~~~^~~
```

## Code

```#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;

const int N = 100005;

vpii event[N]; //second true if he has been caught
bool sol = true;
int ans[N];
vi open;

struct seg{
int a, b, id;
bool operator < (const seg &o) const{
return b > o.b;
}
};

bool cmp(const seg &lhs, const seg &rhs){
return lhs.a < rhs.a;
}

void display(const seg &v){
cout << v.a << " " << v.b << " " << v.id << endl;
}

vector<seg> vec;
priority_queue<seg> pq;

int main(){
int n, k, m, x; char t;
cin >> n >> k >> m;
for(int i = 0; i < m; i++){
cin >> t >> x;
if(t == 'C') event[x].pb({i, true});
else{
event[x].pb({i, false});
open.pb(i);
ans[i] = open.size(); //TO CHANGE
}
}

for(int i = 1; i <= n; i++){
for(int j = 0; j < int(event[i].size()) - 1; j++)
if(event[i][j].se)
vec.pb({event[i][j].fi + 1, event[i][j + 1].fi - 1, i});
if(!event[i].empty() && event[i].back().se) vec.pb({event[i].back().fi + 1, m + 1, i});
}

sort(vec.begin(), vec.end(), cmp);

//for(auto u : vec) display(u);

int idx = 0;
for(int i = 0; i < int(open.size()); i++){
//cout << i << ", " << open[i] << ": " << endl;
while(idx < int(vec.size()) && vec[idx].a <= open[i]) pq.push(vec[idx++]);
int cnt = 0;

//cout << "top: ";
//display(pq.top());

if(pq.empty() || pq.top().b < open[i]){sol = false; break;}
while((i == int(open.size()) - 1 && !pq.empty()) || pq.top().b < open[i + 1]){
cnt++;
ans[pq.top().a - 1] = i + 1;
pq.pop();
}
if(!sol || (cnt = 0 && pq.empty())){sol = false; break;}
if(cnt = 0){
ans[pq.top().a - 1] = i + 1;
pq.pop();
}

}

while(!pq.empty() && sol){
if(pq.top().b != m + 1) sol = false;
ans[pq.top().a - 1] = 1;
pq.pop();
}
for(int i = idx; i < int(vec.size()); i++){
if(vec[i].b != m + 1) sol = false;
ans[vec[i].a - 1] = 1;
}

if(!sol){
cout << "IMPOSSIBLE\n";
return 0;
}

for(int i = 0; i < m; i++)
cout << ans[i] << " ";
cout << endl;
}```

## Test details

### Test 1

Group: 2, 4, 5

Verdict: ACCEPTED

input
```1 1 1 C 1```
view   save

correct output
`1`
view   save

user output
`1`
view   save

### Test 2

Group: 2, 4, 5

Verdict: ACCEPTED

input
```1 1 1 O 1```
view   save

correct output
`IMPOSSIBLE`
view   save

user output
`IMPOSSIBLE`
view   save

### Test 3

Group: 2, 4, 5

Verdict: ACCEPTED

input
```1 1 2 C 1 C 1```
view   save

correct output
`IMPOSSIBLE`
view   save

user output
`IMPOSSIBLE`
view   save

### Test 4

Group: 2, 4, 5

Verdict: ACCEPTED

input
```1 1 2 C 1 O 1```
view   save

correct output
`IMPOSSIBLE`
view   save

user output
`IMPOSSIBLE`
view   save

### Test 5

Group: 2, 4, 5

Verdict: ACCEPTED

input
```1 1 2 O 1 C 1```
view   save

correct output
`IMPOSSIBLE`
view   save

user output
`IMPOSSIBLE`
view   save

### Test 6

Group: 4, 5

Verdict: ACCEPTED

input
```2 1 2 C 1 C 2```
view   save

correct output
`1 1`
view   save

user output
`1 1`
view   save

### Test 7

Group: 4, 5

Verdict: ACCEPTED

input
```2 1 2 C 1 O 1```
view   save

correct output
`IMPOSSIBLE`
view   save

user output
`IMPOSSIBLE`
view   save

### Test 8

Group: 4, 5

Verdict: ACCEPTED

input
```2 1 2 C 1 O 2```
view   save

correct output
`1 1`
view   save

user output
`1 1`
view   save

### Test 9

Group: 1, 3, 4, 5

Verdict: ACCEPTED

input
```3 2 5 C 1 C 2 O 3 C 1 C 2```
view   save

correct output
`1 1 1 1 1`
view   save

user output
`1 1 1 1 1`
view   save

### Test 10

Group: 1, 3, 4, 5

input
```3 2 5 C 1 C 2 O 3 O 3 C 1```
view   save

correct output
`2 1 2 1 1`
view   save

user output
`2 2 1 2 1`
view   save

### Test 11

Group: 1, 3, 4, 5

Verdict: ACCEPTED

input
```3 2 5 C 1 C 2 O 3 O 1 C 1```
view   save

correct output
`2 1 2 1 1`
view   save

user output
`1 2 1 2 1`
view   save

### Test 12

Group: 1, 3, 4, 5

Verdict: ACCEPTED

input
```3 2 5 C 1 C 2 O 1 O 3 C 1```
view   save

correct output
`IMPOSSIBLE`
view   save

user output
`IMPOSSIBLE`
view   save

### Test 13

Group: 1, 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

input
```3 2 4 C 1 O 2 C 1 O 3```
view   save

correct output
`1 1 1 1`
view   save

user output
(empty)
view   save

### Test 14

Group: 1, 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

input
```3 2 4 C 1 O 2 C 2 O 1```
view   save

correct output
`1 1 1 1`
view   save

user output
(empty)
view   save

### Test 15

Group: 1, 3, 4, 5

Verdict: ACCEPTED

input
```3 2 3 C 1 C 2 C 3```
view   save

correct output
`1 1 1`
view   save

user output
`1 1 1`
view   save

### Test 16

Group: 1, 3, 4, 5

Verdict: ACCEPTED

input
```3 2 3 O 1 C 2 C 3```
view   save

correct output
`IMPOSSIBLE`
view   save

user output
`IMPOSSIBLE`
view   save

### Test 17

Group: 1, 2, 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

input
```2 2 7 C 1 O 2 O 2 O 2 O 2 C 1 O 2```
view   save

correct output
`IMPOSSIBLE`
view   save

user output
(empty)
view   save

### Test 18

Group: 1, 3, 4, 5

input
```4 2 5 C 2 O 3 C 1 O 4 C 3```
view   save

correct output
`1 1 1 1 1`
view   save

user output
`2 1 2 2 1`
view   save

### Test 19

Group: 2, 5

Verdict: ACCEPTED

input
```100000 100000 100000 C 1 C 2 C 3 C 4 C 5 C 6 C 7 C 8 C 9 C 10 C 11 C 12 C 13 C 14 C 15 C 16 C 17 C 18 C 19 ...```
view   save

correct output
`50000 49999 49998 49997 49996 ...`
view   save

user output
`1 2 3 4 5 6 7 8 9 10 11 12 13 ...`
view   save

### Test 20

Group: 2, 5

Verdict: ACCEPTED

input
```100000 100000 100000 C 1 C 2 C 3 C 4 C 5 C 6 C 7 C 8 C 9 C 10 C 11 C 12 C 13 C 14 C 15 C 16 C 17 C 18 C 19 ...```
view   save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...`
view   save

user output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...`
view   save

### Test 21

Group: 2, 5

input
```100000 100000 100000 C 1 C 2 C 3 C 4 C 5 C 6 C 7 C 8 C 9 C 10 C 11 C 12 C 13 C 14 C 15 C 16 C 17 C 18 C 19 ...```
view   save

correct output
`20000 20000 20000 20000 20000 ...`
view   save

user output
`20000 20000 20000 20000 20000 ...`
view   save

### Test 22

Group: 5

input
```100000 100 100000 C 1 C 2 C 3 C 4 C 5 C 6 C 7 C 8 C 9 C 10 C 11 C 12 C 13 C 14 C 15 C 16 C 17 C 18 C 19 ...```
view   save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...`
view   save

user output
`100 100 100 100 100 100 100 10...`
view   save

### Test 23

Group: 5

input
```100000 99 100000 C 1 C 2 C 3 C 4 C 5 C 6 C 7 C 8 C 9 C 10 C 11 C 12 C 13 C 14 C 15 C 16 C 17 C 18 C 19 ...```
view   save

correct output
`IMPOSSIBLE`
view   save

user output
`100 100 100 100 100 100 100 10...`
view   save

### Test 24

Group: 3, 4, 5

input
```500 2 500 C 384 O 62 C 387 O 473 C 191 O 341 C 173 O 150 C 283 O 391 C 430 O 53 C 394 O 138 C 422 O 368 C 316 O 375 C 457 ...```
view   save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...`
view   save

user output
`73 1 21 2 33 3 166 4 238 5 76 ...`
view   save

### Test 25

Group: 3, 4, 5

input
```500 2 500 C 384 O 62 C 387 O 473 C 191 O 341 C 173 O 150 C 283 O 391 C 430 O 53 C 394 C 138 C 167 O 342 O 416 C 27 O 140 ...```
view   save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 ...`
view   save

user output
`62 1 170 2 208 3 161 4 208 5 2...`
view   save

### Test 26

Group: 3, 4, 5

input
```500 2 500 C 384 O 62 C 387 O 473 C 191 C 341 C 415 O 331 C 63 O 38 C 430 O 53 C 394 C 138 C 167 O 342 O 416 C 27 O 140 ...```
view   save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 ...`
view   save

user output
`42 1 16 2 71 58 41 3 160 4 160...`
view   save

### Test 27

Group: 3, 4, 5

input
```500 2 500 C 384 O 62 C 387 C 473 C 249 C 268 C 5 C 10 C 412 C 383 C 224 C 323 C 258 C 330 C 284 O 218 C 110 O 29 C 457 ...```
view   save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...`
view   save

user output
`94 1 83 73 74 96 104 9 9 50 14...`
view   save

### Test 28

Group: 4, 5

input
```500 250 500 C 384 O 62 C 387 O 473 C 191 O 341 C 173 O 150 C 283 O 391 C 430 O 53 C 394 O 138 C 422 O 368 C 316 O 375 C 457 ...```
view   save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...`
view   save

user output
`250 1 250 2 250 3 250 4 43 5 2...`
view   save

### Test 29

Group: 4, 5

input
```500 250 500 C 384 O 62 C 387 O 473 C 191 O 341 C 173 O 150 C 283 O 391 C 430 O 53 C 394 C 138 C 167 O 342 O 416 O 374 C 457 ...```
view   save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 2 1 3 ...`
view   save

user output
`248 1 248 2 225 3 79 4 248 5 2...`
view   save

### Test 30

Group: 4, 5

input
```500 250 500 C 384 O 62 C 387 O 473 C 191 C 341 C 415 O 331 C 51 O 78 C 181 O 422 C 267 C 404 C 247 O 478 O 367 O 41 O 208 ...```
view   save

correct output
`1 1 1 1 1 3 2 3 3 2 2 2 5 4 2 ...`
view   save

user output
`30 1 85 2 138 72 118 3 206 4 6...`
view   save

### Test 31

Group: 4, 5

input
```500 250 500 C 384 O 62 C 387 C 473 C 249 C 268 C 5 C 10 C 412 C 383 C 224 C 323 C 258 C 330 C 284 O 218 C 380 O 178 C 448 ...```
view   save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...`
view   save

user output
`109 1 66 76 37 30 109 66 73 54...`
view   save

### Test 32

Group: 2, 4, 5

input
```500 500 500 C 384 O 62 C 387 O 473 C 191 O 341 C 173 O 150 C 283 O 391 C 430 O 53 C 394 O 138 C 422 O 368 C 316 O 375 C 457 ...```
view   save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...`
view   save

user output
`250 1 120 2 250 3 250 4 43 5 2...`
view   save

### Test 33

Group: 2, 4, 5

input
```500 500 500 C 384 O 62 C 387 O 473 C 191 O 341 C 173 O 150 C 283 O 391 C 430 O 53 C 394 C 138 C 167 O 342 O 416 O 374 C 457 ...```
view   save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 2 1 3 ...`
view   save

user output
`248 1 248 2 225 3 171 4 248 5 ...`
view   save

### Test 34

Group: 2, 4, 5

input
```500 500 500 C 384 O 62 C 387 O 473 C 191 C 341 C 415 O 331 C 51 O 78 C 180 O 422 C 267 C 405 C 247 O 478 O 367 O 41 O 207 ...```
view   save

correct output
`1 1 1 1 2 1 3 3 3 2 2 2 2 4 5 ...`
view   save

user output
`37 1 43 2 51 160 32 3 206 4 60...`
view   save

### Test 35

Group: 2, 4, 5

input
```500 500 500 C 384 O 62 C 387 C 473 C 249 C 268 C 5 C 10 C 412 C 383 C 224 C 323 C 258 C 330 C 284 O 218 C 380 O 178 C 448 ...```
view   save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...`
view   save

user output
`17 1 109 109 109 12 45 101 109...`
view   save

### Test 36

Group: 3, 5

input
```100000 2 100000 C 89384 O 54062 C 85387 O 53318 C 68691 O 33602 C 89173 O 585 C 65783 O 67461 C 13930 O 29417 C 61394 O 94608 C 84422 O 6107 C 98316 O 5375 C 59957 ...```
view   save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...`
view   save

user output
`18217 1 20591 2 6172 3 46747 4...`
view   save

### Test 37

Group: 3, 5

input
```100000 2 100000 C 89384 O 54062 C 85387 O 53318 C 68691 O 33602 C 89173 O 585 C 65783 O 67461 C 13930 O 29417 C 61394 C 94608 C 1612 O 21246 O 1312 C 3527 O 79075 ...```
view   save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 ...`
view   save

user output
`14728 1 8376 2 7546 3 10778 4 ...`
view   save

### Test 38

Group: 3, 5

input
```100000 2 100000 C 89384 O 54062 C 85387 O 53318 C 68691 C 33602 C 95255 O 11017 C 69148 O 69798 C 13930 O 29417 C 61394 C 94608 C 1612 O 21246 O 1312 C 3527 O 79075 ...```
view   save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 ...`
view   save

user output
`12287 1 242 2 4404 32504 24507...`
view   save

### Test 39

Group: 3, 5

input
```100000 2 100000 C 89384 O 54062 C 85387 C 53318 C 84358 C 72953 C 1337 C 21450 C 85973 C 81480 C 2059 C 80277 C 67398 C 60273 C 87574 O 96948 C 11799 O 22010 C 59957 ...```
view   save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...`
view   save

user output
`1044 1 8313 9518 18880 16431 1...`
view   save

### Test 40

Group: 5

input
```100000 50000 100000 C 89384 O 54062 C 85387 O 53318 C 68691 O 33602 C 89173 O 585 C 65783 O 67461 C 13930 O 29417 C 61394 O 94608 C 84422 O 6107 C 98316 O 5375 C 59957 ...```
view   save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...`
view   save

user output
`45400 1 372 2 27127 3 49999 4 ...`
view   save

### Test 41

Group: 5

input
```100000 50000 100000 C 89384 O 54062 C 85387 O 53318 C 68691 O 33602 C 89173 O 585 C 65783 O 67461 C 13930 O 29417 C 61394 C 94608 C 1612 O 21246 O 1312 O 5376 C 59957 ...```
view   save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 ...`
view   save

user output
`49999 1 372 2 9118 3 13029 4 4...`
view   save

### Test 42

Group: 5

input
```100000 50000 100000 C 89384 O 54062 C 85387 O 53318 C 68691 C 33602 C 95255 O 11017 C 72513 O 72134 C 35960 O 42131 C 82594 C 27738 C 18802 O 36386 O 4308 O 9071 O 98193 ...```
view   save

correct output
`1 1 1 1 1 3 2 3 3 3 3 3 3 4 5 ...`
view   save

user output
`39939 1 26198 2 39939 30359 37...`
view   save

### Test 43

Group: 5

input
```100000 50000 100000 C 89384 O 54062 C 85387 C 53318 C 84358 C 72953 C 1337 C 21450 C 85973 C 81480 C 2059 C 80277 C 67398 C 60273 C 87574 O 96948 C 16294 O 27555 C 89397 ...```
view   save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...`
view   save

user output
`20160 1 3756 8004 20160 20160 ...`
view   save

### Test 44

Group: 2, 5

input
```100000 100000 100000 C 89384 O 54062 C 85387 O 53318 C 68691 O 33602 C 89173 O 585 C 65783 O 67461 C 13930 O 29417 C 61394 O 94608 C 84422 O 6107 C 98316 O 5375 C 59957 ...```
view   save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...`
view   save

user output
`45400 1 372 2 27127 3 49999 4 ...`
view   save

### Test 45

Group: 2, 5

input
```100000 100000 100000 C 89384 O 54062 C 85387 O 53318 C 68691 O 33602 C 89173 O 585 C 65783 O 67461 C 13930 O 29417 C 61394 C 94608 C 1612 O 21246 O 1312 O 5376 C 59957 ...```
view   save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 ...`
view   save

user output
`18912 1 372 2 9118 3 13029 4 4...`
view   save

### Test 46

Group: 2, 5

input
```100000 100000 100000 C 89384 O 54062 C 85387 O 53318 C 68691 C 33602 C 95255 O 11017 C 72513 O 72134 C 35960 O 42131 C 82594 C 27738 C 18802 O 36386 O 4308 O 9071 O 98193 ...```
view   save

correct output
`1 1 1 1 2 1 3 3 3 3 3 3 4 5 3 ...`
view   save

user output
`13361 1 38171 2 29751 34278 19...`
view   save

### Test 47

Group: 2, 5

```100000 100000 100000 C 89384 O 54062 C 85387 C 53318 C 84358 C 72953 C 1337 C 21450 C 85973 C 81480 C 2059 C 80277 C 67398 C 60273 C 87574 O 96948 C 16294 O 27555 C 89397 ...```
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...`
`20160 1 12493 13974 20160 2900...`