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

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:128:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < del[i].size(); ++j) {
                  ~~^~~~~~~~~~~~~~~
input/code.cpp:157:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < event.size(); ++i) {
                 ~~^~~~~~~~~~~~~~
input/code.cpp:175:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < del[i].size(); ++j) {
                  ~~^~~~~~~~~~~~~~~
input/code.cpp:216: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:229:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ans.size(); ++i) {
                 ~~^~~~~~~~~~~~
input/code.c

Code

#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 fi[N];

int label[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, i});
			} else {
				ord.insert({*(per[g[i]].upper_bound(i)), i});
//				ord.insert({g[i], g[i]});
			}
			continue;
		}
		for(int j = 1; j <= w[i]; ++j) {
			auto it = ord.begin();
			int abb = (*it).second;
			del[i].push_back(abb);
	//		cout << "Adding " << abb << "\n";
			people.erase(g[(*it).second]);
			ord.erase(it);

		}
	}

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

	vector<pair<int, int> > event;

	for(int i = 1; i <= m; ++i) {
		if(t[i] == 'C') continue;
		fi[i] = N;
		for(int j = 0; j < del[i].size(); ++j) {
			int mm = del[i][j];
			fi[i] = min(fi[i], mm);
		}
		event.push_back({fi[i], i});
		event.push_back({i, i});
	}

	sort(event.begin(), event.end());

/*	for(int i = 0; i < event.size(); ++i) {
		cout << event[i].first << " " << event[i].second << "\n";
	}

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

	cout << "\n\n";
*/

	for(int i = 0; i < event.size(); ++i) {
		int a = event[i].first;
		int b = event[i].second;
		if(a == b) {
			fre.insert(label[a]);
			continue;
		}
		if(fre.size() == 0) {
			cout << "IMPOSSIBLE\n";
			return 0;
		}
		int lab = *(fre.begin());
		label[b] = lab;
		fre.erase(fre.begin());
	}

	for(int i = 1; i <= m; ++i) {
		if(t[i] == 'C') continue;
		for(int j = 0; j < del[i].size(); ++j) {
			int mm = del[i][j];
			loc[g[mm]].push_back(label[i]);
		}
		loc[g[i]].push_back(label[i]);
	}


	for(int i = 1; i <= n; ++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";
				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 details

Test 1

Group: 2, 4, 5

Verdict: ACCEPTED

input
1 1 1
C 1

correct output

user output

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
1 2 1 2 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
1 2 1 2 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
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

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

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

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

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

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

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

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

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

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

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 1 2 3 2 2 3 3 3 3 4 5 ...

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

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

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

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 1 2 3 3 3 1 1 1 1 4 5 ...

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

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

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

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

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

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

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

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 1 2 3 2 2 2 2 2 2 4 5 ...

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

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

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

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 1 2 3 3 3 3 3 3 3 4 5 ...

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