# NOI 2019 Open

 Start: N/A End: N/A

CSES - NOI 2019 Open - Results
History
3:01:098
2:53:538
2:35:198
2:33:010
 Task: Thieves and Prisons Sender: pwild Submission time: 2019-03-10 01:05:23 Language: C++ Status: READY Score: 8

## Code

```#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define has(c,i) ((c).find(i) != end(c))
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

struct event {
bool is_cap;
ll who;
};

ll n, k, m;
vector<event> events;

void fail() {
cout << "IMPOSSIBLE" << endl;
exit(0);
}

void solve1() {
assert(k == 2);
bool ok = true;
vl pos(n,-1);
FOR(i,0,m) {
event ev = events[i];
ll p = (mask >> i) & 1;
if (ev.is_cap) {
if (pos[ev.who] != -1) ok = false;
pos[ev.who] = p;
} else {
if (pos[ev.who] != -1) ok = false;
bool freed = false;
FOR(j,0,n) if (pos[j] == p) {
pos[j] = -1;
freed = true;
}
if (!freed) ok = false;
}
}
if (ok) {
FOR(i,0,m) {
ll p = (mask >> i) & 1;
cout << p+1 << " ";
}
cout << endl;
return;
}
}
cout << "IMPOSSIBLE" << endl;
}

void solve2() {
assert(n == k);

set<pll> in_prison;

vector<queue<ll>> person_events(n);
FOR(i,0,m) person_events[events[i].who].push(i);

vl res, pos(n,-1);
FOR(i,0,m) {
auto ev = events[i];
if (ev.is_cap) {
if (pos[ev.who] != -1) fail();
res.pb(ev.who);
ll prio = oo;
auto &q = person_events[ev.who];
while (sz(q) && q.front() <= i) q.pop();
if (sz(q)) prio = q.front();
in_prison.emplace(prio,ev.who);
} else {
if (pos[ev.who] != -1) fail();
if (in_prison.empty()) fail();

ll free = begin(in_prison)->yy;
res.pb(free);
pos[free] = -1;
in_prison.erase(begin(in_prison));
}
}
for (ll x: res) cout << x+1 << " ";
cout << endl;
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);

cin >> n >> k >> m;
events.resize(m);
for (auto &ev: events) {
char c;
cin >> c >> ev.who;
ev.is_cap = c == 'C';
ev.who--;
}

if (max(n,m) <= 10 && k == 2) {
solve1();
} else if (n == k) {
solve2();
} else {
cout << "IMPOSSIBLE" << 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

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

correct output
`IMPOSSIBLE`
view   save

user output
`1 1`
view   save

### Test 4

Group: 2, 4, 5

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

correct output
`IMPOSSIBLE`
view   save

user output
`1 1`
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

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

correct output
`1 1`
view   save

user output
`IMPOSSIBLE`
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

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

correct output
`1 1`
view   save

user output
`IMPOSSIBLE`
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

Verdict: ACCEPTED

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 1 2 1 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
`2 1 2 1 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: ACCEPTED

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

correct output
`1 1 1 1`
view   save

user output
`1 1 1 1`
view   save

### Test 14

Group: 1, 3, 4, 5

Verdict: ACCEPTED

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

correct output
`1 1 1 1`
view   save

user output
`1 1 1 1`
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: ACCEPTED

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
`IMPOSSIBLE`
view   save

### Test 18

Group: 1, 3, 4, 5

Verdict: ACCEPTED

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

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 2 3 4 5 6 7 8 9 10 11 12 13 ...`
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
`1 2 3 4 5 6 7 8 9 10 11 12 13 ...`
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
`IMPOSSIBLE`
view   save

### Test 23

Group: 5

Verdict: ACCEPTED

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
`IMPOSSIBLE`
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
`IMPOSSIBLE`
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
`IMPOSSIBLE`
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
`IMPOSSIBLE`
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
`IMPOSSIBLE`
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
`IMPOSSIBLE`
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
`IMPOSSIBLE`
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
`IMPOSSIBLE`
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
`IMPOSSIBLE`
view   save

### Test 32

Group: 2, 4, 5

Verdict: ACCEPTED

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
`384 384 387 387 191 191 173 17...`
view   save

### Test 33

Group: 2, 4, 5

Verdict: ACCEPTED

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
`384 384 387 387 191 191 173 17...`
view   save

### Test 34

Group: 2, 4, 5

Verdict: ACCEPTED

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
`384 384 387 387 191 341 415 41...`
view   save

### Test 35

Group: 2, 4, 5

Verdict: ACCEPTED

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
`384 384 387 473 249 268 5 10 4...`
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
`IMPOSSIBLE`
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
`IMPOSSIBLE`
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
`IMPOSSIBLE`
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
`IMPOSSIBLE`
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
`IMPOSSIBLE`
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
`IMPOSSIBLE`
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
`IMPOSSIBLE`
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
`IMPOSSIBLE`
view   save

### Test 44

Group: 2, 5

Verdict: ACCEPTED

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
`89384 89384 85387 85387 68691 ...`
view   save

### Test 45

Group: 2, 5

Verdict: ACCEPTED

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
`89384 89384 85387 85387 68691 ...`
view   save

### Test 46

Group: 2, 5

Verdict: ACCEPTED

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
`89384 89384 85387 85387 68691 ...`
view   save

### Test 47

Group: 2, 5

Verdict: ACCEPTED

input
```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 ...```
view   save

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

user output
`89384 89384 85387 53318 84358 ...`
view   save