CSES - NOI 2019 Open - Results
Submission details
Task:Thieves and Prisons
Sender:egor.lifar
Submission time:2019-03-09 21:30:12 +0200
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED8
#2ACCEPTED13
#3ACCEPTED14
#4ACCEPTED18
#5ACCEPTED47
Test results
testverdicttimegroup
#1ACCEPTED0.02 s2, 4, 5details
#2ACCEPTED0.02 s2, 4, 5details
#3ACCEPTED0.01 s2, 4, 5details
#4ACCEPTED0.01 s2, 4, 5details
#5ACCEPTED0.02 s2, 4, 5details
#6ACCEPTED0.02 s4, 5details
#7ACCEPTED0.01 s4, 5details
#8ACCEPTED0.01 s4, 5details
#9ACCEPTED0.02 s1, 3, 4, 5details
#10ACCEPTED0.01 s1, 3, 4, 5details
#11ACCEPTED0.01 s1, 3, 4, 5details
#12ACCEPTED0.01 s1, 3, 4, 5details
#13ACCEPTED0.03 s1, 3, 4, 5details
#14ACCEPTED0.01 s1, 3, 4, 5details
#15ACCEPTED0.03 s1, 3, 4, 5details
#16ACCEPTED0.02 s1, 3, 4, 5details
#17ACCEPTED0.02 s1, 2, 3, 4, 5details
#18ACCEPTED0.01 s1, 3, 4, 5details
#19ACCEPTED0.09 s2, 5details
#20ACCEPTED0.07 s2, 5details
#21ACCEPTED0.09 s2, 5details
#22ACCEPTED0.04 s5details
#23ACCEPTED0.04 s5details
#24ACCEPTED0.02 s3, 4, 5details
#25ACCEPTED0.01 s3, 4, 5details
#26ACCEPTED0.02 s3, 4, 5details
#27ACCEPTED0.01 s3, 4, 5details
#28ACCEPTED0.02 s4, 5details
#29ACCEPTED0.02 s4, 5details
#30ACCEPTED0.02 s4, 5details
#31ACCEPTED0.03 s4, 5details
#32ACCEPTED0.01 s2, 4, 5details
#33ACCEPTED0.01 s2, 4, 5details
#34ACCEPTED0.02 s2, 4, 5details
#35ACCEPTED0.01 s2, 4, 5details
#36ACCEPTED0.06 s3, 5details
#37ACCEPTED0.07 s3, 5details
#38ACCEPTED0.05 s3, 5details
#39ACCEPTED0.05 s3, 5details
#40ACCEPTED0.07 s5details
#41ACCEPTED0.07 s5details
#42ACCEPTED0.07 s5details
#43ACCEPTED0.06 s5details
#44ACCEPTED0.08 s2, 5details
#45ACCEPTED0.08 s2, 5details
#46ACCEPTED0.09 s2, 5details
#47ACCEPTED0.08 s2, 5details

Code

 /*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>

using namespace std;
template<typename T1, typename T2> inline void chkmin(T1 &a, T2 b) {if (a > b) a = b;}
template<typename T1, typename T2> inline void chkmax(T1 &a, T2 b) {if (a < b) a = b;}
#define files(FILENAME) read(FILENAME); write(FILENAME)
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define left left228
#define right right228
#define y1 y1228
#define mp make_pair
#define pb push_back
#define y2 y2228
const string FILENAME = "input";
const int MAXN = 100228;


int n, k, m;
char c[MAXN];
int x[MAXN];
int res[MAXN];
int last[MAXN];


int  main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//read(FILENAME);
	cin >> n >> k >> m;
	for (int i = 0; i < m; i++) {
		cin >> c[i] >> x[i];
	}
	set<int> s;
	for (int i = 1; i <= k; i++) {
		s.insert(i);
	}
	for (int i = 1; i <= n; i++) {
		last[i] = m + 1;
	}
	set<pair<int, int> > st;
	int lasts = 1;
	int times = m;
	for (int i = m - 1; i >= 0; i--) {
		if (c[i] == 'O') {
			if (s.empty()) {
				cout << "IMPOSSIBLE\n";
				return 0;
			}
			int f = *s.begin();
			s.erase(f);
			st.insert(make_pair(i, f));
			lasts = f;
			res[i] = f;
			times = i;
		} else {
			auto it = st.lower_bound(make_pair(last[x[i]], 0));
			if (it != st.begin()) {
				it--;
				pair<int, int> f = *it;
				st.erase(f);
				res[i] = f.second;
				s.insert(f.second);
			} else {
			//	cout << lasts << ' ' << times << ' ' << last[x[i]] <<  ' ' << x[i] << endl;
				//cout << times << endl;
				if (times >= last[x[i]]) {
					cout << "IMPOSSIBLE\n";
					return 0;
				}
				res[i] = lasts;
			}
		}
		last[x[i]] = i;
	}
	if (!st.empty()) {
		cout << "IMPOSSIBLE\n";
		return 0;
	}
	for (int i = 0; i < m; i++) {
		cout << res[i] << '\n';
	}
 	return 0; 
}

Test details

Test 1

Group: 2, 4, 5

Verdict: ACCEPTED

input
1 1 1
C 1

correct output

user output
1

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
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
50000
49999
49998
49997
49996
...
Truncated

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
1
1
1
1
1
...
Truncated

Test 21

Group: 2, 5

Verdict: ACCEPTED

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

correct output
20000 20000 20000 20000 20000 ...

user output
20000
20000
20000
20000
20000
...
Truncated

Test 22

Group: 5

Verdict: ACCEPTED

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
100
100
100
100
100
...
Truncated

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

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
1
1
1
1
1
...
Truncated

Test 25

Group: 3, 4, 5

Verdict: ACCEPTED

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
1
1
1
1
1
...
Truncated

Test 26

Group: 3, 4, 5

Verdict: ACCEPTED

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
1
1
1
1
1
...
Truncated

Test 27

Group: 3, 4, 5

Verdict: ACCEPTED

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
1
1
1
1
1
...
Truncated

Test 28

Group: 4, 5

Verdict: ACCEPTED

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
1
1
1
1
1
...
Truncated

Test 29

Group: 4, 5

Verdict: ACCEPTED

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
1
1
1
1
1
...
Truncated

Test 30

Group: 4, 5

Verdict: ACCEPTED

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
1
1
1
1
3
...
Truncated

Test 31

Group: 4, 5

Verdict: ACCEPTED

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
1
1
1
1
1
...
Truncated

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
1
1
1
1
1
...
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
1
1
1
1
1
...
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
1
1
1
1
3
...
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
1
1
1
1
1
...
Truncated

Test 36

Group: 3, 5

Verdict: ACCEPTED

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
1
1
1
1
1
...
Truncated

Test 37

Group: 3, 5

Verdict: ACCEPTED

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
1
1
1
1
1
...
Truncated

Test 38

Group: 3, 5

Verdict: ACCEPTED

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
1
1
1
1
1
...
Truncated

Test 39

Group: 3, 5

Verdict: ACCEPTED

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
1
1
1
1
1
...
Truncated

Test 40

Group: 5

Verdict: ACCEPTED

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
1
1
1
1
1
...
Truncated

Test 41

Group: 5

Verdict: ACCEPTED

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
1
1
1
1
1
...
Truncated

Test 42

Group: 5

Verdict: ACCEPTED

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
1
1
1
1
3
...
Truncated

Test 43

Group: 5

Verdict: ACCEPTED

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
1
1
1
1
1
...
Truncated

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
1
1
1
1
1
...
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
1
1
1
1
1
...
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
1
1
1
1
3
...
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
1
1
1
1
1
...
Truncated