CSES - NOI 2019 Open - Results
Submission details
Task:Thieves and Prisons
Sender:pwild
Submission time:2019-03-10 01:05:23 +0200
Language:C++
Status:READY
Result:8
Feedback
groupverdictscore
#1ACCEPTED8
#20
#30
#40
#50
Test results
testverdicttimegroup
#1ACCEPTED0.01 s2, 4, 5details
#2ACCEPTED0.01 s2, 4, 5details
#30.02 s2, 4, 5details
#40.01 s2, 4, 5details
#5ACCEPTED0.01 s2, 4, 5details
#60.01 s4, 5details
#7ACCEPTED0.02 s4, 5details
#80.02 s4, 5details
#9ACCEPTED0.02 s1, 3, 4, 5details
#10ACCEPTED0.01 s1, 3, 4, 5details
#11ACCEPTED0.02 s1, 3, 4, 5details
#12ACCEPTED0.02 s1, 3, 4, 5details
#13ACCEPTED0.02 s1, 3, 4, 5details
#14ACCEPTED0.01 s1, 3, 4, 5details
#15ACCEPTED0.01 s1, 3, 4, 5details
#16ACCEPTED0.01 s1, 3, 4, 5details
#17ACCEPTED0.01 s1, 2, 3, 4, 5details
#18ACCEPTED0.01 s1, 3, 4, 5details
#19ACCEPTED0.11 s2, 5details
#200.14 s2, 5details
#210.12 s2, 5details
#220.04 s5details
#23ACCEPTED0.04 s5details
#240.02 s3, 4, 5details
#250.02 s3, 4, 5details
#260.01 s3, 4, 5details
#270.02 s3, 4, 5details
#280.01 s4, 5details
#290.02 s4, 5details
#300.01 s4, 5details
#310.02 s4, 5details
#32ACCEPTED0.02 s2, 4, 5details
#33ACCEPTED0.01 s2, 4, 5details
#34ACCEPTED0.01 s2, 4, 5details
#35ACCEPTED0.01 s2, 4, 5details
#360.04 s3, 5details
#370.04 s3, 5details
#380.04 s3, 5details
#390.04 s3, 5details
#400.03 s5details
#410.04 s5details
#420.04 s5details
#430.04 s5details
#44ACCEPTED0.12 s2, 5details
#45ACCEPTED0.11 s2, 5details
#46ACCEPTED0.12 s2, 5details
#47ACCEPTED0.16 s2, 5details

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);
	FOR(mask,0,1 << m) {
		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

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:

input
1 1 2
C 1
C 1

correct output
IMPOSSIBLE

user output
1 1 

Test 4

Group: 2, 4, 5

Verdict:

input
1 1 2
C 1
O 1

correct output
IMPOSSIBLE

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

input
2 1 2
C 1
C 2

correct output
1 1 

user output
IMPOSSIBLE

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:

input
2 1 2
C 1
O 2

correct output
1 1 

user output
IMPOSSIBLE

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

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

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

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: 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
384 384 387 387 191 191 173 17...
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
384 384 387 387 191 191 173 17...
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
384 384 387 387 191 341 415 41...
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
384 384 387 473 249 268 5 10 4...
Truncated

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: 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
89384 89384 85387 85387 68691 ...
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
89384 89384 85387 85387 68691 ...
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
89384 89384 85387 85387 68691 ...
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
89384 89384 85387 53318 84358 ...
Truncated