Thieves and Prisons

input/code.cpp: In function 'int main()':
input/code.cpp:124:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < del[i].size(); ++j) {
                  ~~^~~~~~~~~~~~~~~
input/code.cpp:167:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0; j < cont[ans[i-1]].size(); ++j) {
                   ~~^~~~~~~~~~~~~~~~~~~~~~~
input/code.cpp:180:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ans.size(); ++i) {
                 ~~^~~~~~~~~~~~
input/code.cpp:190:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < del[i].size(); ++j) {
                  ~~^~~~~~~~~~~~~~~

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 1e5 + 5;

typedef pair<int, int> pii;
typedef long long ll;

set<int> per[N];

int pri[N];
int mi[N];
int w[N];

vector<int> del[N];
set<int> fre;


vector<int> loc[N];

bool impri[N];
vector<int> cont[N];

int main() {
	int n, k, m;
	cin >> n >> k >> m;
	vector<int> g;
	vector<char> t;
	g.push_back(-1);
	t.push_back(-1);
	for(int i = 1; i <= m; ++i) {
		char a; int b;
		cin >> a >> b;
		t.push_back(a);
		g.push_back(b);
		per[b].insert(i);
		if(b > n) {
			cout << "IMPOSSIBLE\n";
			return 0;
		}
	}


	if(t[1] == 'C') {
		pri[1] = 1;
	} else {
		cout << "IMPOSSIBLE\n";
		return 0;
	}

	for(int i = 2; i <= m; ++i) {
		if(t[i] == 'C') {
			pri[i] = pri[i-1] + 1;
		} else {
			pri[i] = pri[i-1] - 1;
		}
	}
	mi[m] = pri[m];
	for(int i = m-1; i >= 1; --i) {
		mi[i] = min(mi[i+1], pri[i]);
	}

	if(mi[1] < 0) {
		cout << "IMPOSSIBLE\n";
		return 0;
	}

	int ext = 0;
	int curPri = 0;
	for(int i = 1; i <= m; ++i) {
		if(t[i] == 'C') {
			++curPri;
			continue;
		}
		w[i] = min(mi[i] + 1 - ext, curPri);
		curPri -= w[i];
		ext += w[i] - 1;

	}

	set<pair<int, int> > ord;
	set<int> people;

	for(int i = 1; i <= m; ++i) {
		if(t[i] == 'C') {
			if(people.count(g[i]) > 0) {
				cout << "IMPOSSIBLE\n";
				return 0;
			}
			people.insert(g[i]);
			set<int>::iterator it = per[g[i]].upper_bound(i);
			if(it == per[g[i]].end()) {
				ord.insert({N, g[i]});
			} else {
				ord.insert({*(per[g[i]].upper_bound(i)), g[i]});
			}
			continue;
		}
		for(int j = 1; j <= w[i]; ++j) {
			auto it = ord.begin();
			del[i].push_back((*it).second);
			people.erase((*it).second);
			ord.erase(it);

		}
	}

	for(int i = 1; i <= k; ++i) {
		fre.insert(i);
	}

	for(int i = 1; i <= m; ++i) {
		if(t[i] == 'C') continue;
		if(fre.size() == 0) {
			cout << "IMPOSSIBLE\n";
			return 0;
		}
		int pr = *(fre.begin());
		fre.erase(fre.begin());
		for(int j = 0; j < del[i].size(); ++j) {
			int mm = del[i][j];
			loc[mm].push_back(pr);
			continue;
		}
		loc[g[i]].push_back(pr);
	}

	for(int i = 1; i <= m; ++i) {
		reverse(loc[i].begin(), loc[i].end());
	}

/*	for(int i = 1; i <= n; ++i) {
		cout << "The prisons for " << i << ": ";
		for(int j = 0; j < loc[i].size(); ++j) {
			cout << loc[i][j] << " ";
		}
		cout << "\n";
	}
*/
	vector<int> ans;
	for(int i = 1; i <= m; ++i) {
		if(loc[g[i]].size() == 0) {
			ans.push_back(1);
		} else {
			ans.push_back(loc[g[i]][loc[g[i]].size() - 1]);
			loc[g[i]].pop_back();
		}

		if(t[i] == 'C') {
			cont[ans[i-1]].push_back(g[i]);
			if(impri[g[i]]) {
				cout << "IMPOSSIBLE\n";
				return 0;
			}
			impri[g[i]] = true;
		} else {
			if(impri[g[i]]) {
				cout << "IMPOSSIBLE\n";
				cout << "ere\n";
				cout << g[i] << "\n";
				return 0;
			}
			for(int j = 0; j < cont[ans[i-1]].size(); ++j) {
				int abb = cont[ans[i-1]][j];
				if(!impri[abb]) {
					cout << "IMPOSSIBLE\n";
					return 0;
				}
				impri[abb] = false;
			}
			cont[ans[i-1]].clear();

		}
	}

	for(int i = 0; i < ans.size(); ++i) {
		cout << ans[i] << " ";
	}

	cout << "\n";
	return 0;

	cout << "\n\n";
	for(int i = 1; i <= m; ++i) {
		cout << del[i].size() << ": ";
		for(int j = 0; j < del[i].size(); ++j) {
			cout << del[i][j] << " ";
		}
		cout << "\n";
	}



}

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

Test 25

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 26

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 27

Group: 3, 4, 5

Verdict: WRONG ANSWER

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

Test 37

Group: 3, 5

Verdict: WRONG ANSWER

Test 38

Group: 3, 5

Verdict: WRONG ANSWER

Test 39

Group: 3, 5

Verdict: WRONG ANSWER

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