Thieves and Prisons

input/code.cpp:3:0: warning: ignoring #pragma region Libraries [-Wunknown-pragmas]
 #pragma region Libraries
 
input/code.cpp:19:0: warning: ignoring #pragma endregion  [-Wunknown-pragmas]
 #pragma endregion

using namespace std;

#pragma region Libraries

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <cstring>
#include <iomanip>

#pragma endregion

#define MP make_pair
#define all(v) v.begin(), v.end()
#define trav(it,v) for (auto it = v.begin(); it != v.end(); it++)
#define rep(index, from, to) for (int index = from; index < to; index++)
#define ll long long
#define pi pair<int,int>

int32_t main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int n, k, m;
	cin >> n >> k >> m;
	vector<pair<char, int>> mo(m);
	vector<stack<int>> ca(n, stack<int>());
	for (int i = 0; i < m; i++)
	{
		cin >> mo[i].first >> mo[i].second;
		mo[i].second--;

		if (mo[i].first == 'C') {
			ca[mo[i].second].push(i);
		}
	}
	priority_queue<pair<int, int>> pq;
	for (int i = 0; i < n; i++)
	{
		if (ca[i].size()) {
			pq.push(MP(ca[i].top(), i));
			ca[i].pop();
		}
	}
	reverse(all(mo));
	vector<int> ans(m);
	unordered_set<int> avapri;
	for (int i = 0; i < k; i++)
	{
		avapri.insert(i + 1);
	}
	int prev = 1;
	for (int i = 0; i < m; i++)
	{
		if (mo[i].first == 'O') {
			if (avapri.size() == 0) {
				cout << "IMPOSSIBLE" << endl;
				return 0;
			}
			int pri = *avapri.begin();
			avapri.erase(pri);
			while (pq.size() && (m - pq.top().first - 1 < i || ans[m - pq.top().first - 1] != 0)) {
				pair<int, int> p = pq.top();
				pq.pop();
				if (ca[p.second].size() > 0) {
					pq.push(MP(ca[p.second].top(), p.second));
					ca[p.second].pop();
				}
			}
			if (pq.size() == 0 || (pq.size() == 1 && pq.top().second == mo[i].second)) {
				cout << "IMPOSSIBLE" << endl;
				return 0;
			}
			else if (pq.size() == 1 || mo[i].second != pq.top().second) {
				pair<int, int> p = pq.top();
				pq.pop();
				ans[m - 1 - p.first] = pri;
				ans[i] = pri;
				if (ca[p.second].size() > 0) {
					pq.push(MP(ca[p.second].top(), p.second));
					ca[p.second].pop();
				}
			}
			else {
				if (pq.top().second == mo[i].second) {
					pair<int, int> temp = pq.top();
					pq.pop();
					pair<int, int> p = pq.top();
					pq.pop();
					ans[m - p.first - 1] = pri;
					ans[i] = pri;
					if (ca[p.second].size() > 0) {
						pq.push(MP(ca[p.second].top(), p.second));
						ca[p.second].pop();
					}
					pq.push(temp);
				}
			}
			prev = pri;
		}
		else {
			if (ans[i] != 0) {
				avapri.insert(ans[i]);
				continue;
			}
			ans[i] = prev;
		}
	}
	reverse(all(ans));
	reverse(all(mo));
	vector<vector<int>> prison(k + 1, vector<int>());
	vector<bool> inpri(n);
	for (int i = 0; i < m; i++)
	{
		if (inpri[mo[i].second]) {
			cout << "IMPOSSIBLE" << endl;
			return 0;
		}
		if (mo[i].first == 'O') {
			if (prison[ans[i]].size() == 0) {
				cout << "IMPOSSIBLE" << endl;
				return 0;
			}
			trav(it, prison[ans[i]]) {
				inpri[*it] = 0;
			}
			prison[ans[i]].clear();
		}
		else {
			prison[ans[i]].push_back(mo[i].second);
			inpri[mo[i].second] = 1;
		}
	}
	for (int i = 0; i < m; i++)
	{
		cout << ans[i] << " ";
	}


#ifdef _DEBUG
	system("pause");
#endif // _DEBUG
	return 0;
}

Test 1

Group: 2, 4, 5

Verdict: ACCEPTED

Test 2

Group: 2, 4, 5

Verdict: ACCEPTED

Test 3

Group: 2, 4, 5

Verdict: ACCEPTED

Test 4

Group: 2, 4, 5

Verdict: ACCEPTED

Test 5

Group: 2, 4, 5

Verdict: ACCEPTED

Test 6

Group: 4, 5

Verdict: ACCEPTED

Test 7

Group: 4, 5

Verdict: ACCEPTED

Test 8

Group: 4, 5

Verdict: ACCEPTED

Test 9

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 10

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 11

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 12

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 13

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 14

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 15

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 16

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 17

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 18

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 19

Group: 2, 5

Verdict: ACCEPTED

Test 20

Group: 2, 5

Verdict: ACCEPTED

Test 21

Group: 2, 5

Verdict: ACCEPTED

Test 22

Group: 5

Verdict: ACCEPTED

Test 23

Group: 5

Verdict: ACCEPTED

Test 24

Group: 3, 4, 5

Verdict: ACCEPTED

Test 25

Group: 3, 4, 5

Verdict: ACCEPTED

Test 26

Group: 3, 4, 5

Verdict: ACCEPTED

Test 27

Group: 3, 4, 5

Verdict: ACCEPTED

Test 28

Group: 4, 5

Verdict: ACCEPTED

Test 29

Group: 4, 5

Verdict: ACCEPTED

Test 30

Group: 4, 5

Verdict: ACCEPTED

Test 31

Group: 4, 5

Verdict: ACCEPTED

Test 32

Group: 2, 4, 5

Verdict: ACCEPTED

Test 33

Group: 2, 4, 5

Verdict: ACCEPTED

Test 34

Group: 2, 4, 5

Verdict: ACCEPTED

Test 35

Group: 2, 4, 5

Verdict: ACCEPTED

Test 36

Group: 3, 5

Verdict: ACCEPTED

Test 37

Group: 3, 5

Verdict: ACCEPTED

Test 38

Group: 3, 5

Verdict: ACCEPTED

Test 39

Group: 3, 5

Verdict: ACCEPTED

Test 40

Group: 5

Verdict: ACCEPTED

Test 41

Group: 5

Verdict: ACCEPTED

Test 42

Group: 5

Verdict: ACCEPTED

Test 43

Group: 5

Verdict: ACCEPTED

Test 44

Group: 2, 5

Verdict: ACCEPTED

Test 45

Group: 2, 5

Verdict: ACCEPTED

Test 46

Group: 2, 5

Verdict: ACCEPTED

Test 47

Group: 2, 5

Verdict: ACCEPTED