CSES - Putka Open 2015 – finaali - Results
Submission details
Task:Ravintola
Sender:
Submission time:2015-12-20 16:52:38 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.05 s1details
#20.05 s1details
#30.06 s1details
#40.05 s1details
#50.05 s1details
#60.04 s2details
#70.05 s2details
#80.05 s2details
#90.06 s2details
#100.05 s2details
#110.22 s3details
#120.19 s3details
#130.21 s3details
#140.18 s3details
#150.20 s3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:51:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(j+step < foo.size() && foo[j+step].e <= foo[i].s) {
                 ^
input/code.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int64_t i=0;i<events.size();i++) {
                    ^
input/code.cpp:73:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int64_t i=0;i<bar.size();i++) {
                    ^

Code

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct argh {
int64_t s,e,id;
};
bool operator<(const argh &a1, const argh &a2) {
if(a1.e < a2.e) return true;
if(a1.e == a2.e && a1.s < a2.s) return true;
if(a1.e == a2.e && a1.s == a2.s && a1.id < a2.id) return true;
return false;
}
struct ev {
int64_t t, type, id;
};
bool operator<(const ev &a1, const ev &a2) {
if(a1.t < a2.t) return true;
if(a1.t == a2.t && a1.type < a2.type) return true;
if(a1.t == a2.t && a1.type == a2.type && a1.id < a2.id) return true;
return false;
}
int main(void)
{
int64_t n;
cin >> n;
vector<argh> foo(n);
vector<ev> events;
for(int64_t i=0;i<n;i++) {
int64_t a,b;
cin >> a >> b;
foo[i]=argh{a,b,i};
events.push_back(ev{a, 1, i});
events.push_back(ev{b, 0, i});
}
sort(foo.begin(), foo.end());
sort(events.begin(), events.end());
int64_t m=0;
for(int64_t i=0;i<n;i++) {
//search from start to foo[i].b
//i.e. find last thing whose end is <= start
int64_t j=0;
for(int64_t step=((int64_t)1<<(int64_t)30);step>=1;step/=2) {
if(j+step < foo.size() && foo[j+step].e <= foo[i].s) {
j+=step;
}
}
j++;
m=max(m, i-j+1);
}
cout << m << endl;
vector<int> tables(m,0);
int64_t ti=0;
vector<int64_t> bar(n);
for(int64_t i=0;i<events.size();i++) {
if(events[i].type) {
while(tables[ti] != 0) {
ti=(ti+1)%tables.size();
}
tables[ti]=1;
bar[events[i].id]=ti;
} else {
tables[bar[events[i].id]]=0;
}
}
for(int64_t i=0;i<bar.size();i++) {
cout << bar[i]+1 << '\n';
}
return 0;
}

Test details

Test 1

Group: 1

Verdict:

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

correct output
6
5
5
2
1
...

user output
7
6
6
1
7
...

Test 2

Group: 1

Verdict:

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

correct output
4
1
1
3
1
...

user output
7
7
3
2
1
...

Test 3

Group: 1

Verdict:

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

correct output
5
5
4
3
3
...

user output
6
1
5
3
5
...

Test 4

Group: 1

Verdict:

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

correct output
6
6
3
4
1
...

user output
8
7
4
1
8
...

Test 5

Group: 1

Verdict:

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

correct output
5
2
2
2
2
...

user output
9
2
2
2
2
...

Test 6

Group: 2

Verdict:

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

correct output
358
264
215
218
262
...

user output
979
427
739
402
328
...

Test 7

Group: 2

Verdict:

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

correct output
393
181
151
140
63
...

user output
983
461
782
837
65
...

Test 8

Group: 2

Verdict:

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

correct output
388
115
358
93
170
...

user output
983
702
614
700
634
...

Test 9

Group: 2

Verdict:

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

correct output
368
287
36
225
114
...

user output
983
368
744
273
768
...

Test 10

Group: 2

Verdict:

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

correct output
384
240
215
156
163
...

user output
919
280
248
768
360
...

Test 11

Group: 3

Verdict:

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

correct output
36779
4699
7608
7073
23546
...

user output
99897
78448
7885
87683
48097
...

Test 12

Group: 3

Verdict:

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

correct output
36979
5145
5964
3813
17811
...

user output
99776
95154
6149
3883
51951
...

Test 13

Group: 3

Verdict:

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

correct output
36760
17563
24436
3901
1722
...

user output
99955
19577
69739
92342
1732
...

Test 14

Group: 3

Verdict:

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

correct output
36633
5062
11088
8773
23538
...

user output
99902
79197
44445
87985
41947
...

Test 15

Group: 3

Verdict:

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

correct output
36920
28994
8379
21303
3304
...

user output
99901
66207
8796
24670
3367
...