Thieves and Prisons

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define N (1<<18)
#define M 1000000007
#define P complex<long long>
#define X real()
#define Y imag()

using namespace std;

int n, k, m, ep[101010], viimVankE[101010], vangittu[101010], vankilaNro[101010];
set<pair<int,int>> vank[101010];
set<int> tVank; // Tyhjä vankila vapautusaika_vankilaId
priority_queue<int> vva[101010]; // Vankilan vapautusajat negatiivisina
set<int> vangitut, tyhjatV;
char et[101010];

void ei() {
	cout << "IMPOSSIBLE";
	exit(0);
}

int main() {
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	cin >> n >> k >> m;
	for(int i=1; i<=m; i++) {
		cin >> et[i];
		cin >> ep[i];
	}

	//Numeroi vankilat
	int cnt = 1;
	for(int i=1; i<=m; i++) {
		if(et[i] == 'O') {
			vankilaNro[i] = cnt;
			cnt++;
			if(cnt>k)
				cnt = 1;
		}
	}
	// Vangit vankiloihin
	int viimVapVank = 0;
	for(int i=m; i>=1; i--) {
		if(et[i] == 'O') {
			viimVapVank = i; // viimeisin vapaa vankila
			viimVankE[ep[i]] = i-1; // Tämän vangin oltava tällöin vapaa että voi avata
		} else { // napataan vanki
			if(!viimVapVank && viimVankE[ep[i]]) // ei vankilaa josta vapautetan
				ei();
			if(viimVapVank) {
				if(viimVankE[ep[i]] && viimVapVank > viimVankE[ep[i]]) // huom ei >=
					ei();
				if(viimVankE[ep[i]]) { // pitää vapautua x mennessä
					vank[viimVapVank].insert(make_pair(viimVankE[ep[i]], ep[i])); // oltava vapaa x, vanki y
				} else { // ei rajaa
					vank[viimVapVank].insert(make_pair(1e9, ep[i])); // oltava vapaa x, vanki y
				}
			}
			viimVankE[ep[i]] = i-1; // Tämän vangin oltava tällöin vapaa(että voidaan napata)
		}
	}
	// Siirto seuraaviin
	for(int i=m; i>=1; i--) {
		if(et[i] == 'O') {
			if(vank[i].size() == 0) { // Vankila tyhjä
				if(tyhjatV.find(vankilaNro[i]) != tyhjatV.end()) {
					// Edellinen tyhjä ei ehtinyt täyttyä
					ei();
				}
				tVank.insert(i);
				tyhjatV.insert(vankilaNro[i]);
			} else { // vankilassa ehkä siirrettäviä vankeja, siirretään vankeja tyhjiin vankiloihin ensimmäisenä viimeiseen tyhjään 
				auto it = vank[i].end();
				it--;
				vector<pair<int,int>> poisTasta;
				while(it != vank[i].begin()) { // ei siirretä ekaa koskaan että joku jää
					auto it2 = tVank.upper_bound((*it).first);
					if(it2 != tVank.begin()) {
						it2--;
						// Siirretään it2 vankilaan
						vank[*it2].insert(*it);
						poisTasta.push_back(*it);
						tyhjatV.erase(vankilaNro[*it2]);
						tVank.erase(it2);
					}
					it--;	
				}
				for(auto u:poisTasta)
					vank[i].erase(u);
			
			}
		}
	}
	// Testataan onko validi ja muodostetaan vastaus
	// 1. vapautuvat vankilat ei tyhjiä
	vector<int> ans;
	for(int i=m; i>=1; i--) {
		if(et[i] == 'O') {
			if(vank[i].size() == 0)
				ei();
			for(auto u:vank[i]) {
				vangittu[u.second] = vankilaNro[i];
			}
			ans.push_back(vankilaNro[i]);
		} else {
			ans.push_back(vangittu[i]);
		}
	}
	reverse(ans.begin(), ans.end());
	for(auto u:ans) {
		if(u)
		cout << u << " ";
		else
			cout << 1 << " ";
	}
}

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

Test 14

Group: 1, 3, 4, 5

Verdict: WRONG ANSWER

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

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

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

Test 29

Group: 4, 5

Verdict: WRONG ANSWER

Test 30

Group: 4, 5

Verdict: WRONG ANSWER

Test 31

Group: 4, 5

Verdict: WRONG ANSWER

Test 32

Group: 2, 4, 5

Verdict: WRONG ANSWER

Test 33

Group: 2, 4, 5

Verdict: WRONG ANSWER

Test 34

Group: 2, 4, 5

Verdict: WRONG ANSWER

Test 35

Group: 2, 4, 5

Verdict: WRONG ANSWER

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

Test 41

Group: 5

Verdict: WRONG ANSWER

Test 42

Group: 5

Verdict: WRONG ANSWER

Test 43

Group: 5

Verdict: WRONG ANSWER

Test 44

Group: 2, 5

Verdict: WRONG ANSWER

Test 45

Group: 2, 5

Verdict: WRONG ANSWER

Test 46

Group: 2, 5

Verdict: WRONG ANSWER

Test 47

Group: 2, 5

Verdict: WRONG ANSWER