Code Submission Evaluation System Login

NOI 2019 Open

Start:N/A
End:N/A
 

Tasks | Scoreboard | Statistics


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

Feedback

groupverdictscore
#1ACCEPTED8
#2WRONG ANSWER0
#3WRONG ANSWER0
#4WRONG ANSWER0
#5WRONG ANSWER0

Test results

testverdicttime (s)group
#1ACCEPTED0.01 / 1.002, 4, 5details
#2ACCEPTED0.01 / 1.002, 4, 5details
#3WRONG ANSWER0.02 / 1.002, 4, 5details
#4WRONG ANSWER0.01 / 1.002, 4, 5details
#5ACCEPTED0.01 / 1.002, 4, 5details
#6WRONG ANSWER0.01 / 1.004, 5details
#7ACCEPTED0.02 / 1.004, 5details
#8WRONG ANSWER0.02 / 1.004, 5details
#9ACCEPTED0.02 / 1.001, 3, 4, 5details
#10ACCEPTED0.01 / 1.001, 3, 4, 5details
#11ACCEPTED0.02 / 1.001, 3, 4, 5details
#12ACCEPTED0.02 / 1.001, 3, 4, 5details
#13ACCEPTED0.02 / 1.001, 3, 4, 5details
#14ACCEPTED0.01 / 1.001, 3, 4, 5details
#15ACCEPTED0.01 / 1.001, 3, 4, 5details
#16ACCEPTED0.01 / 1.001, 3, 4, 5details
#17ACCEPTED0.01 / 1.001, 2, 3, 4, 5details
#18ACCEPTED0.01 / 1.001, 3, 4, 5details
#19ACCEPTED0.11 / 1.002, 5details
#20WRONG ANSWER0.14 / 1.002, 5details
#21WRONG ANSWER0.12 / 1.002, 5details
#22WRONG ANSWER0.04 / 1.005details
#23ACCEPTED0.04 / 1.005details
#24WRONG ANSWER0.02 / 1.003, 4, 5details
#25WRONG ANSWER0.02 / 1.003, 4, 5details
#26WRONG ANSWER0.01 / 1.003, 4, 5details
#27WRONG ANSWER0.02 / 1.003, 4, 5details
#28WRONG ANSWER0.01 / 1.004, 5details
#29WRONG ANSWER0.02 / 1.004, 5details
#30WRONG ANSWER0.01 / 1.004, 5details
#31WRONG ANSWER0.02 / 1.004, 5details
#32ACCEPTED0.02 / 1.002, 4, 5details
#33ACCEPTED0.01 / 1.002, 4, 5details
#34ACCEPTED0.01 / 1.002, 4, 5details
#35ACCEPTED0.01 / 1.002, 4, 5details
#36WRONG ANSWER0.04 / 1.003, 5details
#37WRONG ANSWER0.04 / 1.003, 5details
#38WRONG ANSWER0.04 / 1.003, 5details
#39WRONG ANSWER0.04 / 1.003, 5details
#40WRONG ANSWER0.03 / 1.005details
#41WRONG ANSWER0.04 / 1.005details
#42WRONG ANSWER0.04 / 1.005details
#43WRONG ANSWER0.04 / 1.005details
#44ACCEPTED0.12 / 1.002, 5details
#45ACCEPTED0.11 / 1.002, 5details
#46ACCEPTED0.12 / 1.002, 5details
#47ACCEPTED0.16 / 1.002, 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

view   save

correct output


view   save

user output


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: WRONG ANSWER

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

Verdict: WRONG ANSWER

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

Verdict: WRONG ANSWER

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

Verdict: WRONG ANSWER

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
...
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
...
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
...
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
...
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
...
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
...
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
...
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: WRONG ANSWER

input
100000 100000 100000
C 1
C 2
C 3
C 4
...
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

Verdict: WRONG ANSWER

input
100000 100000 100000
C 1
C 2
C 3
C 4
...
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

Verdict: WRONG ANSWER

input
100000 100 100000
C 1
C 2
C 3
C 4
...
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
...
view   save

correct output
IMPOSSIBLE

view   save

user output
IMPOSSIBLE

view   save

Test 24

Group: 3, 4, 5

Verdict: WRONG ANSWER

input
500 2 500
C 384
O 62
C 387
O 473
...
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

Verdict: WRONG ANSWER

input
500 2 500
C 384
O 62
C 387
O 473
...
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

Verdict: WRONG ANSWER

input
500 2 500
C 384
O 62
C 387
O 473
...
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

Verdict: WRONG ANSWER

input
500 2 500
C 384
O 62
C 387
C 473
...
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

Verdict: WRONG ANSWER

input
500 250 500
C 384
O 62
C 387
O 473
...
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

Verdict: WRONG ANSWER

input
500 250 500
C 384
O 62
C 387
O 473
...
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

Verdict: WRONG ANSWER

input
500 250 500
C 384
O 62
C 387
O 473
...
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

Verdict: WRONG ANSWER

input
500 250 500
C 384
O 62
C 387
C 473
...
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
...
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
...
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
...
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
...
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

Verdict: WRONG ANSWER

input
100000 2 100000
C 89384
O 54062
C 85387
O 53318
...
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

Verdict: WRONG ANSWER

input
100000 2 100000
C 89384
O 54062
C 85387
O 53318
...
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

Verdict: WRONG ANSWER

input
100000 2 100000
C 89384
O 54062
C 85387
O 53318
...
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

Verdict: WRONG ANSWER

input
100000 2 100000
C 89384
O 54062
C 85387
C 53318
...
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

Verdict: WRONG ANSWER

input
100000 50000 100000
C 89384
O 54062
C 85387
O 53318
...
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

Verdict: WRONG ANSWER

input
100000 50000 100000
C 89384
O 54062
C 85387
O 53318
...
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

Verdict: WRONG ANSWER

input
100000 50000 100000
C 89384
O 54062
C 85387
O 53318
...
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

Verdict: WRONG ANSWER

input
100000 50000 100000
C 89384
O 54062
C 85387
C 53318
...
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
...
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
...
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
...
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
...
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