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