CSES - APIO 2016 - Results
Submission details
Task:Gap
Sender:ollpu
Submission time:2019-04-13 18:34:54 +0300
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED30
#2ACCEPTED70
Test results
testverdicttimescoregroup
#1ACCEPTED0.02 s301details
#2ACCEPTED0.02 s301details
#3ACCEPTED0.01 s301details
#4ACCEPTED0.02 s301details
#5ACCEPTED0.01 s301details
#6ACCEPTED0.01 s301details
#7ACCEPTED0.03 s301details
#8ACCEPTED0.02 s301details
#9ACCEPTED0.03 s301details
#10ACCEPTED0.01 s301details
#11ACCEPTED0.02 s301details
#12ACCEPTED0.03 s301details
#13ACCEPTED0.01 s301details
#14ACCEPTED0.04 s301details
#15ACCEPTED0.02 s301details
#16ACCEPTED0.05 s301details
#17ACCEPTED0.05 s301details
#18ACCEPTED0.06 s301details
#19ACCEPTED0.06 s301details
#20ACCEPTED0.04 s301details
#21ACCEPTED0.15 s301details
#22ACCEPTED0.15 s301details
#23ACCEPTED0.15 s301details
#24ACCEPTED0.15 s301details
#25ACCEPTED0.13 s301details
#26ACCEPTED0.15 s301details
#27ACCEPTED0.15 s301details
#28ACCEPTED0.15 s301details
#29ACCEPTED0.15 s301details
#30ACCEPTED0.11 s301details
#31ACCEPTED0.02 s301details
#32ACCEPTED0.03 s301details
#33ACCEPTED0.03 s702details
#34ACCEPTED0.02 s702details
#35ACCEPTED0.02 s702details
#36ACCEPTED0.02 s702details
#37ACCEPTED0.02 s702details
#38ACCEPTED0.02 s702details
#39ACCEPTED0.02 s702details
#40ACCEPTED0.02 s702details
#41ACCEPTED0.02 s702details
#42ACCEPTED0.02 s702details
#43ACCEPTED0.03 s702details
#44ACCEPTED0.02 s702details
#45ACCEPTED0.02 s702details
#46ACCEPTED0.02 s702details
#47ACCEPTED0.02 s702details
#48ACCEPTED0.05 s702details
#49ACCEPTED0.05 s702details
#50ACCEPTED0.04 s702details
#51ACCEPTED0.05 s702details
#52ACCEPTED0.04 s702details
#53ACCEPTED0.13 s702details
#54ACCEPTED0.12 s702details
#55ACCEPTED0.13 s702details
#56ACCEPTED0.12 s702details
#57ACCEPTED0.10 s702details
#58ACCEPTED0.13 s702details
#59ACCEPTED0.13 s702details
#60ACCEPTED0.13 s702details
#61ACCEPTED0.13 s702details
#62ACCEPTED0.08 s702details
#63ACCEPTED0.02 s702details
#64ACCEPTED0.01 s702details

Compiler report

input/code.cpp: In function 'long long int findGap(int, int)':
input/code.cpp:9:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (a.size() < n) {
            ~~~~~~~~~^~~

Code

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
const long inf = 1e18;
long long findGap(int t, int n) { // int ??
  if (t == 1) {
    set<long> a;
    long s = 0, t = inf;
    while (a.size() < n) {
      long long ns, nt;
      MinMax(s, t, &ns, &nt);
      a.insert(ns);
      a.insert(nt);
      s = ns+1;
      t = nt-1;
    }
    long la = -1;
    long res = 0;
    for (long ta : a) {
      if (la != -1) {
        res = max(res, ta-la);
      }
      la = ta;
    }
    return res;
  } else {
    long long b, e;
    MinMax(0, inf, &b, &e);
    long step = (e-b)/(n-1) + !!((e-b)%(n-1));
    long res = step;
    long lm = b, ku = b;
    while (ku < e) {
      long long mn, mx;
      MinMax(ku+1, ku+step, &mn, &mx);
      if (mn != -1) {
        res = max(res, long(mn-lm));
        lm = mx;
      }
      ku = ku+step;
    }
    return res;
  }
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
1 2
29659227736649406 728704890713...

correct output
(empty)

user output
30

Test 2

Group: 1

Verdict: ACCEPTED

input
1 15
4910834401530995 8236651085889...

correct output
(empty)

user output
30

Test 3

Group: 1

Verdict: ACCEPTED

input
1 15
26822012613602297 830163366163...

correct output
(empty)

user output
30

Test 4

Group: 1

Verdict: ACCEPTED

input
1 15
9924552505919890 2065094604777...

correct output
(empty)

user output
30

Test 5

Group: 1

Verdict: ACCEPTED

input
1 15
5829742 7847985 9866228 118844...

correct output
(empty)

user output
30

Test 6

Group: 1

Verdict: ACCEPTED

input
1 100
3343298378001251 1748440243612...

correct output
(empty)

user output
30

Test 7

Group: 1

Verdict: ACCEPTED

input
1 100
6615965004180765 1318520746045...

correct output
(empty)

user output
30

Test 8

Group: 1

Verdict: ACCEPTED

input
1 100
709357564623321 77128246965710...

correct output
(empty)

user output
30

Test 9

Group: 1

Verdict: ACCEPTED

input
1 100
14237546663715875 268988673144...

correct output
(empty)

user output
30

Test 10

Group: 1

Verdict: ACCEPTED

input
1 100
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
(empty)

user output
30

Test 11

Group: 1

Verdict: ACCEPTED

input
1 1500
393226341882178 13216496468619...

correct output
(empty)

user output
30

Test 12

Group: 1

Verdict: ACCEPTED

input
1 1500
276387254568267 34829856602130...

correct output
(empty)

user output
30

Test 13

Group: 1

Verdict: ACCEPTED

input
1 1500
394502620394491 47759565208720...

correct output
(empty)

user output
30

Test 14

Group: 1

Verdict: ACCEPTED

input
1 1500
232644703989174 91492562377220...

correct output
(empty)

user output
30

Test 15

Group: 1

Verdict: ACCEPTED

input
1 1500
5829742 7847985 9866228 118844...

correct output
(empty)

user output
30

Test 16

Group: 1

Verdict: ACCEPTED

input
1 25000
9133780858698 37909498824529 4...

correct output
(empty)

user output
30

Test 17

Group: 1

Verdict: ACCEPTED

input
1 25000
95371433023390 183850194127179...

correct output
(empty)

user output
30

Test 18

Group: 1

Verdict: ACCEPTED

input
1 25000
7504645895952 60172453317399 8...

correct output
(empty)

user output
30

Test 19

Group: 1

Verdict: ACCEPTED

input
1 25000
39499604978204 102114332324801...

correct output
(empty)

user output
30

Test 20

Group: 1

Verdict: ACCEPTED

input
1 25000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
(empty)

user output
30

Test 21

Group: 1

Verdict: ACCEPTED

input
1 100000
4488179349610 16973330836139 4...

correct output
(empty)

user output
30

Test 22

Group: 1

Verdict: ACCEPTED

input
1 100000
13149709307416 18293717155215 ...

correct output
(empty)

user output
30

Test 23

Group: 1

Verdict: ACCEPTED

input
1 100000
5111699493996 19396274992433 2...

correct output
(empty)

user output
30

Test 24

Group: 1

Verdict: ACCEPTED

input
1 100000
12448126808805 14955287440308 ...

correct output
(empty)

user output
30

Test 25

Group: 1

Verdict: ACCEPTED

input
1 100000
5829742 7847985 9866228 118844...

correct output
(empty)

user output
30

Test 26

Group: 1

Verdict: ACCEPTED

input
1 100000
15609355723226 28246203120916 ...

correct output
(empty)

user output
30

Test 27

Group: 1

Verdict: ACCEPTED

input
1 100000
10126035265316 18812438778817 ...

correct output
(empty)

user output
30

Test 28

Group: 1

Verdict: ACCEPTED

input
1 100000
5196984998043 10787031331530 5...

correct output
(empty)

user output
30

Test 29

Group: 1

Verdict: ACCEPTED

input
1 100000
19821024745776 35883956869682 ...

correct output
(empty)

user output
30

Test 30

Group: 1

Verdict: ACCEPTED

input
1 100000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
(empty)

user output
30

Test 31

Group: 1

Verdict: ACCEPTED

input
1 118
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
(empty)

user output
30

Test 32

Group: 1

Verdict: ACCEPTED

input
1 118
1 500000000000000001 750000000...

correct output
(empty)

user output
30

Test 33

Group: 2

Verdict: ACCEPTED

input
2 2
78103569500113815 605712887753...

correct output
(empty)

user output
70

Test 34

Group: 2

Verdict: ACCEPTED

input
2 15
61436558421029682 834292060079...

correct output
(empty)

user output
70

Test 35

Group: 2

Verdict: ACCEPTED

input
2 15
59675445208809451 142100938168...

correct output
(empty)

user output
70

Test 36

Group: 2

Verdict: ACCEPTED

input
2 15
57755783461204076 725499461376...

correct output
(empty)

user output
70

Test 37

Group: 2

Verdict: ACCEPTED

input
2 15
5829742 7847985 9866228 118844...

correct output
(empty)

user output
70

Test 38

Group: 2

Verdict: ACCEPTED

input
2 100
4935323238097746 2853421336222...

correct output
(empty)

user output
70

Test 39

Group: 2

Verdict: ACCEPTED

input
2 100
329840134021571 35247166734885...

correct output
(empty)

user output
70

Test 40

Group: 2

Verdict: ACCEPTED

input
2 100
20951091854749146 393866653367...

correct output
(empty)

user output
70

Test 41

Group: 2

Verdict: ACCEPTED

input
2 100
8683327277022804 1152589874346...

correct output
(empty)

user output
70

Test 42

Group: 2

Verdict: ACCEPTED

input
2 100
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
(empty)

user output
70

Test 43

Group: 2

Verdict: ACCEPTED

input
2 1500
1618213394018307 1726930763754...

correct output
(empty)

user output
70

Test 44

Group: 2

Verdict: ACCEPTED

input
2 1500
423747667147233 15612870327743...

correct output
(empty)

user output
70

Test 45

Group: 2

Verdict: ACCEPTED

input
2 1500
64452176748519 137423800315192...

correct output
(empty)

user output
70

Test 46

Group: 2

Verdict: ACCEPTED

input
2 1500
324495733956306 33247199518693...

correct output
(empty)

user output
70

Test 47

Group: 2

Verdict: ACCEPTED

input
2 1500
5829742 7847985 9866228 118844...

correct output
(empty)

user output
70

Test 48

Group: 2

Verdict: ACCEPTED

input
2 25000
112605853915943 12530590767415...

correct output
(empty)

user output
70

Test 49

Group: 2

Verdict: ACCEPTED

input
2 25000
53697824651228 59941694110355 ...

correct output
(empty)

user output
70

Test 50

Group: 2

Verdict: ACCEPTED

input
2 25000
236383646331590 30973864010249...

correct output
(empty)

user output
70

Test 51

Group: 2

Verdict: ACCEPTED

input
2 25000
52783945537122 62819045853889 ...

correct output
(empty)

user output
70

Test 52

Group: 2

Verdict: ACCEPTED

input
2 25000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
(empty)

user output
70

Test 53

Group: 2

Verdict: ACCEPTED

input
2 100000
3977422187752 9172657585884 24...

correct output
(empty)

user output
70

Test 54

Group: 2

Verdict: ACCEPTED

input
2 100000
13262637344137 25327517069541 ...

correct output
(empty)

user output
70

Test 55

Group: 2

Verdict: ACCEPTED

input
2 100000
18832120122902 29507339632281 ...

correct output
(empty)

user output
70

Test 56

Group: 2

Verdict: ACCEPTED

input
2 100000
6181561812375 6378266039481 17...

correct output
(empty)

user output
70

Test 57

Group: 2

Verdict: ACCEPTED

input
2 100000
5829742 7847985 9866228 118844...

correct output
(empty)

user output
70

Test 58

Group: 2

Verdict: ACCEPTED

input
2 100000
535929232534 21492335528903 25...

correct output
(empty)

user output
70

Test 59

Group: 2

Verdict: ACCEPTED

input
2 100000
9057012105366 20678972320055 2...

correct output
(empty)

user output
70

Test 60

Group: 2

Verdict: ACCEPTED

input
2 100000
7697039304820 22564329077790 2...

correct output
(empty)

user output
70

Test 61

Group: 2

Verdict: ACCEPTED

input
2 100000
39366590558911 39585546629301 ...

correct output
(empty)

user output
70

Test 62

Group: 2

Verdict: ACCEPTED

input
2 100000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
(empty)

user output
70

Test 63

Group: 2

Verdict: ACCEPTED

input
2 118
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
(empty)

user output
70

Test 64

Group: 2

Verdict: ACCEPTED

input
2 118
1 500000000000000001 750000000...

correct output
(empty)

user output
70