CSES - Putka Open 2015 – finaali - Results
Submission details
Task:Ravintola
Sender:
Submission time:2015-12-20 13:57:12 +0200
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED15
#2ACCEPTED41
#3ACCEPTED44
Test results
testverdicttimegroup
#1ACCEPTED0.05 s1details
#2ACCEPTED0.06 s1details
#3ACCEPTED0.06 s1details
#4ACCEPTED0.06 s1details
#5ACCEPTED0.05 s1details
#6ACCEPTED0.05 s2details
#7ACCEPTED0.05 s2details
#8ACCEPTED0.05 s2details
#9ACCEPTED0.05 s2details
#10ACCEPTED0.06 s2details
#11ACCEPTED0.17 s3details
#12ACCEPTED0.18 s3details
#13ACCEPTED0.17 s3details
#14ACCEPTED0.18 s3details
#15ACCEPTED0.18 s3details

Code

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define ll long long

using namespace std;

int main () {
	int n;
	cin>>n;
	//vector<pair<int, int>> v(n);
	vector<pair<int, pair<int, int>>> o(2 * n);
	for (int i = 0; i < n; i++) {
		int a, b;
		cin>>a>>b;
		//v[i] = make_pair(a, b);
		o[2 * i] = make_pair(a, make_pair(1, i));
		o[2 * i + 1] = make_pair(b, make_pair(-1, i));
	}
	int c = 0;
	int m = 0;	
	sort(o.begin(), o.end());
	
	priority_queue<int> q;
	for (int i = 0; i < 100000; i++) q.push(-i);
	//cout<<q.top()<<endl;
	int v[n];
	for (pair<int, pair<int, int>> p : o) {
		c += p.second.first;
		m = max(m, c);
		if (p.second.first == 1) {
			v[p.second.second] = q.top();
			q.pop();
		} else {
			q.push(v[p.second.second]);
		}
	}

	cout<<m<<"\n";
	for (int i : v) cout<<-i + 1<<"\n";
	
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
10
78 83
61 70
95 100
84 100
...

correct output
6
5
5
2
1
...

user output
6
5
5
2
1
...

Test 2

Group: 1

Verdict: ACCEPTED

input
10
90 98
99 100
96 100
3 47
...

correct output
4
1
1
3
1
...

user output
4
1
1
3
1
...

Test 3

Group: 1

Verdict: ACCEPTED

input
10
65 87
89 97
32 53
53 73
...

correct output
5
5
4
3
3
...

user output
5
5
4
3
3
...

Test 4

Group: 1

Verdict: ACCEPTED

input
10
54 68
50 60
87 89
85 98
...

correct output
6
6
3
4
1
...

user output
6
6
3
4
1
...

Test 5

Group: 1

Verdict: ACCEPTED

input
10
53 54
41 47
56 68
6 23
...

correct output
5
2
2
2
2
...

user output
5
2
2
2
2
...

Test 6

Group: 2

Verdict: ACCEPTED

input
1000
421639537 911563318
736166797 959945771
397431507 584367626
330835287 620406496
...

correct output
358
264
215
218
262
...

user output
358
264
215
218
262
...

Test 7

Group: 2

Verdict: ACCEPTED

input
1000
452773897 489658400
791565174 873685909
837939163 961670907
54444659 861374731
...

correct output
393
181
151
140
63
...

user output
393
181
151
140
63
...

Test 8

Group: 2

Verdict: ACCEPTED

input
1000
689073468 881081127
613328959 683799585
688380485 930935455
629559449 915788743
...

correct output
388
115
358
93
170
...

user output
388
115
358
93
170
...

Test 9

Group: 2

Verdict: ACCEPTED

input
1000
376658209 496021591
750793088 930681206
293307485 666877615
774206996 816529147
...

correct output
368
287
36
225
114
...

user output
368
287
36
225
114
...

Test 10

Group: 2

Verdict: ACCEPTED

input
1000
273998160 725204323
241875005 614630291
765984835 939309031
345615468 836277449
...

correct output
384
240
215
156
163
...

user output
384
240
215
156
163
...

Test 11

Group: 3

Verdict: ACCEPTED

input
100000
784035755 893627685
78761690 459329957
877042231 976087228
479438596 515807337
...

correct output
36779
4699
7608
7073
23546
...

user output
36779
4699
7608
7073
23546
...

Test 12

Group: 3

Verdict: ACCEPTED

input
100000
952007928 998571741
60494193 790262572
37935588 450716710
518464251 658961939
...

correct output
36979
5145
5964
3813
17811
...

user output
36979
5145
5964
3813
17811
...

Test 13

Group: 3

Verdict: ACCEPTED

input
100000
195552215 647391707
698053972 908728728
923590842 940850158
17166936 129136741
...

correct output
36760
17563
24436
3901
1722
...

user output
36760
17563
24436
3901
1722
...

Test 14

Group: 3

Verdict: ACCEPTED

input
100000
792681664 892304133
442916094 984949977
880260482 922213143
417012279 978533731
...

correct output
36633
5062
11088
8773
23538
...

user output
36633
5062
11088
8773
23538
...

Test 15

Group: 3

Verdict: ACCEPTED

input
100000
662244341 835857878
88360474 126816291
245452241 989480216
32665049 226410123
...

correct output
36920
28994
8379
21303
3304
...

user output
36920
28994
8379
21303
3304
...