CSES - APIO 2016

Submission details
Task:	Gap
Sender:	Yytsi
Submission time:	2019-04-14 15:40:18 +0300
Language:	C++
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	30
#2	ACCEPTED	70

Test results
test	verdict	time	score	group
#1	ACCEPTED	0.03 s	30	1	details
#2	ACCEPTED	0.02 s	30	1	details
#3	ACCEPTED	0.01 s	30	1	details
#4	ACCEPTED	0.01 s	30	1	details
#5	ACCEPTED	0.01 s	30	1	details
#6	ACCEPTED	0.02 s	30	1	details
#7	ACCEPTED	0.01 s	30	1	details
#8	ACCEPTED	0.02 s	30	1	details
#9	ACCEPTED	0.02 s	30	1	details
#10	ACCEPTED	0.01 s	30	1	details
#11	ACCEPTED	0.02 s	30	1	details
#12	ACCEPTED	0.02 s	30	1	details
#13	ACCEPTED	0.02 s	30	1	details
#14	ACCEPTED	0.02 s	30	1	details
#15	ACCEPTED	0.02 s	30	1	details
#16	ACCEPTED	0.06 s	30	1	details
#17	ACCEPTED	0.06 s	30	1	details
#18	ACCEPTED	0.06 s	30	1	details
#19	ACCEPTED	0.06 s	30	1	details
#20	ACCEPTED	0.04 s	30	1	details
#21	ACCEPTED	0.12 s	30	1	details
#22	ACCEPTED	0.12 s	30	1	details
#23	ACCEPTED	0.12 s	30	1	details
#24	ACCEPTED	0.12 s	30	1	details
#25	ACCEPTED	0.10 s	30	1	details
#26	ACCEPTED	0.11 s	30	1	details
#27	ACCEPTED	0.13 s	30	1	details
#28	ACCEPTED	0.12 s	30	1	details
#29	ACCEPTED	0.12 s	30	1	details
#30	ACCEPTED	0.08 s	30	1	details
#31	ACCEPTED	0.01 s	30	1	details
#32	ACCEPTED	0.02 s	30	1	details
#33	ACCEPTED	0.02 s	70	2	details
#34	ACCEPTED	0.01 s	70	2	details
#35	ACCEPTED	0.02 s	70	2	details
#36	ACCEPTED	0.01 s	70	2	details
#37	ACCEPTED	0.01 s	70	2	details
#38	ACCEPTED	0.02 s	70	2	details
#39	ACCEPTED	0.03 s	70	2	details
#40	ACCEPTED	0.02 s	70	2	details
#41	ACCEPTED	0.01 s	70	2	details
#42	ACCEPTED	0.02 s	70	2	details
#43	ACCEPTED	0.02 s	70	2	details
#44	ACCEPTED	0.04 s	70	2	details
#45	ACCEPTED	0.02 s	70	2	details
#46	ACCEPTED	0.01 s	70	2	details
#47	ACCEPTED	0.02 s	70	2	details
#48	ACCEPTED	0.06 s	70	2	details
#49	ACCEPTED	0.05 s	70	2	details
#50	ACCEPTED	0.05 s	70	2	details
#51	ACCEPTED	0.05 s	70	2	details
#52	ACCEPTED	0.04 s	70	2	details
#53	ACCEPTED	0.12 s	70	2	details
#54	ACCEPTED	0.12 s	70	2	details
#55	ACCEPTED	0.12 s	70	2	details
#56	ACCEPTED	0.13 s	70	2	details
#57	ACCEPTED	0.10 s	70	2	details
#58	ACCEPTED	0.12 s	70	2	details
#59	ACCEPTED	0.12 s	70	2	details
#60	ACCEPTED	0.12 s	70	2	details
#61	ACCEPTED	0.13 s	70	2	details
#62	ACCEPTED	0.08 s	70	2	details
#63	ACCEPTED	0.02 s	70	2	details
#64	ACCEPTED	0.02 s	70	2	details

Code

#include "gap.h" // oopsie
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F first
#define S second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;

ll findGap(int T, int N) {
  if (T == 1) {
    ll v[N];
    int a = 0, b = N - 1;
    ll s = 0, t = 1e18, mn, mx;
    while (a <= b) {
      MinMax(s, t, &mn, &mx);
      v[a] = mn;
      v[b] = mx;
      // a . . . . b  N = 6
      // ) a . . b (  N = 6
      // ) ) a b ( (  N = 6
      s = mn + 1; // s > mn
      t = mx - 1; // t < mx
      a++;
      b--;
    }
    ll res = 0;
    FOR(i,0,N-1) res = max(res, v[i+1] - v[i]);
    return res;
  } else {
    ll s = 0, t = 1e18;
    ll mn, mx;
    MinMax(s, t, &mn, &mx);

    if (N == 2) return mx - mn;

    ll len = mx - mn + 1;
    s = mn + 1;
    ll pr = mn, res = 0;
    // iterate over the array in (i+1, i) pairs
    FOR(i,0,N-1) {
      //  s
      // (X X) jump 
      //    t
      t = s + len / (N - 1);
      MinMax(s, t, &mn, &mx);

      if (mn != -1) {
        res = max(res, mn - pr);
        pr = mx;
      }

      // jump after prev group
      // (X X) jump
      //    t
      s = t + 1;
    }

    return res;
  }
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
`1 2 29659227736649406 728704890713...` view save

correct output
(empty)

user output
`30` view save

Test 2

Group: 1

Verdict: ACCEPTED

input
`1 15 4910834401530995 8236651085889...` view save

correct output
(empty)

user output
`30` view save

Test 3

Group: 1

Verdict: ACCEPTED

input
`1 15 26822012613602297 830163366163...` view save

correct output
(empty)

user output
`30` view save

Test 4

Group: 1

Verdict: ACCEPTED

input
`1 15 9924552505919890 2065094604777...` view save

correct output
(empty)

user output
`30` view save

Test 5

Group: 1

Verdict: ACCEPTED

input
`1 15 5829742 7847985 9866228 118844...` view save

correct output
(empty)

user output
`30` view save

Test 6

Group: 1

Verdict: ACCEPTED

input
`1 100 3343298378001251 1748440243612...` view save

correct output
(empty)

user output
`30` view save

Test 7

Group: 1

Verdict: ACCEPTED

input
`1 100 6615965004180765 1318520746045...` view save

correct output
(empty)

user output
`30` view save

Test 8

Group: 1

Verdict: ACCEPTED

input
`1 100 709357564623321 77128246965710...` view save

correct output
(empty)

user output
`30` view save

Test 9

Group: 1

Verdict: ACCEPTED

input
`1 100 14237546663715875 268988673144...` view save

correct output
(empty)

user output
`30` view save

Test 10

Group: 1

Verdict: ACCEPTED

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

correct output
(empty)

user output
`30` view save

Test 11

Group: 1

Verdict: ACCEPTED

input
`1 1500 393226341882178 13216496468619...` view save

correct output
(empty)

user output
`30` view save

Test 12

Group: 1

Verdict: ACCEPTED

input
`1 1500 276387254568267 34829856602130...` view save

correct output
(empty)

user output
`30` view save

Test 13

Group: 1

Verdict: ACCEPTED

input
`1 1500 394502620394491 47759565208720...` view save

correct output
(empty)

user output
`30` view save

Test 14

Group: 1

Verdict: ACCEPTED

input
`1 1500 232644703989174 91492562377220...` view save

correct output
(empty)

user output
`30` view save

Test 15

Group: 1

Verdict: ACCEPTED

input
`1 1500 5829742 7847985 9866228 118844...` view save

correct output
(empty)

user output
`30` view save

Test 16

Group: 1

Verdict: ACCEPTED

input
`1 25000 9133780858698 37909498824529 4...` view save

correct output
(empty)

user output
`30` view save

Test 17

Group: 1

Verdict: ACCEPTED

input
`1 25000 95371433023390 183850194127179...` view save

correct output
(empty)

user output
`30` view save

Test 18

Group: 1

Verdict: ACCEPTED

input
`1 25000 7504645895952 60172453317399 8...` view save

correct output
(empty)

user output
`30` view save

Test 19

Group: 1

Verdict: ACCEPTED

input
`1 25000 39499604978204 102114332324801...` view save

correct output
(empty)

user output
`30` view save

Test 20

Group: 1

Verdict: ACCEPTED

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

correct output
(empty)

user output
`30` view save

Test 21

Group: 1

Verdict: ACCEPTED

input
`1 100000 4488179349610 16973330836139 4...` view save

correct output
(empty)

user output
`30` view save

Test 22

Group: 1

Verdict: ACCEPTED

input
`1 100000 13149709307416 18293717155215 ...` view save

correct output
(empty)

user output
`30` view save

Test 23

Group: 1

Verdict: ACCEPTED

input
`1 100000 5111699493996 19396274992433 2...` view save

correct output
(empty)

user output
`30` view save

Test 24

Group: 1

Verdict: ACCEPTED

input
`1 100000 12448126808805 14955287440308 ...` view save

correct output
(empty)

user output
`30` view save

Test 25

Group: 1

Verdict: ACCEPTED

input
`1 100000 5829742 7847985 9866228 118844...` view save

correct output
(empty)

user output
`30` view save

Test 26

Group: 1

Verdict: ACCEPTED

input
`1 100000 15609355723226 28246203120916 ...` view save

correct output
(empty)

user output
`30` view save

Test 27

Group: 1

Verdict: ACCEPTED

input
`1 100000 10126035265316 18812438778817 ...` view save

correct output
(empty)

user output
`30` view save

Test 28

Group: 1

Verdict: ACCEPTED

input
`1 100000 5196984998043 10787031331530 5...` view save

correct output
(empty)

user output
`30` view save

Test 29

Group: 1

Verdict: ACCEPTED

input
`1 100000 19821024745776 35883956869682 ...` view save

correct output
(empty)

user output
`30` view save

Test 30

Group: 1

Verdict: ACCEPTED

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

correct output
(empty)

user output
`30` view save

Test 31

Group: 1

Verdict: ACCEPTED

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

correct output
(empty)

user output
`30` view save

Test 32

Group: 1

Verdict: ACCEPTED

input
`1 118 1 500000000000000001 750000000...` view save

correct output
(empty)

user output
`30` view save

Test 33

Group: 2

Verdict: ACCEPTED

input
`2 2 78103569500113815 605712887753...` view save

correct output
(empty)

user output
`70` view save

Test 34

Group: 2

Verdict: ACCEPTED

input
`2 15 61436558421029682 834292060079...` view save

correct output
(empty)

user output
`70` view save

Test 35

Group: 2

Verdict: ACCEPTED

input
`2 15 59675445208809451 142100938168...` view save

correct output
(empty)

user output
`70` view save

Test 36

Group: 2

Verdict: ACCEPTED

input
`2 15 57755783461204076 725499461376...` view save

correct output
(empty)

user output
`70` view save

Test 37

Group: 2

Verdict: ACCEPTED

input
`2 15 5829742 7847985 9866228 118844...` view save

correct output
(empty)

user output
`70` view save

Test 38

Group: 2

Verdict: ACCEPTED

input
`2 100 4935323238097746 2853421336222...` view save

correct output
(empty)

user output
`70` view save

Test 39

Group: 2

Verdict: ACCEPTED

input
`2 100 329840134021571 35247166734885...` view save

correct output
(empty)

user output
`70` view save

Test 40

Group: 2

Verdict: ACCEPTED

input
`2 100 20951091854749146 393866653367...` view save

correct output
(empty)

user output
`70` view save

Test 41

Group: 2

Verdict: ACCEPTED

input
`2 100 8683327277022804 1152589874346...` view save

correct output
(empty)

user output
`70` view save

Test 42

Group: 2

Verdict: ACCEPTED

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

correct output
(empty)

user output
`70` view save

Test 43

Group: 2

Verdict: ACCEPTED

input
`2 1500 1618213394018307 1726930763754...` view save

correct output
(empty)

user output
`70` view save

Test 44

Group: 2

Verdict: ACCEPTED

input
`2 1500 423747667147233 15612870327743...` view save

correct output
(empty)

user output
`70` view save

Test 45

Group: 2

Verdict: ACCEPTED

input
`2 1500 64452176748519 137423800315192...` view save

correct output
(empty)

user output
`70` view save

Test 46

Group: 2

Verdict: ACCEPTED

input
`2 1500 324495733956306 33247199518693...` view save

correct output
(empty)

user output
`70` view save

Test 47

Group: 2

Verdict: ACCEPTED

input
`2 1500 5829742 7847985 9866228 118844...` view save

correct output
(empty)

user output
`70` view save

Test 48

Group: 2

Verdict: ACCEPTED

input
`2 25000 112605853915943 12530590767415...` view save

correct output
(empty)

user output
`70` view save

Test 49

Group: 2

Verdict: ACCEPTED

input
`2 25000 53697824651228 59941694110355 ...` view save

correct output
(empty)

user output
`70` view save

Test 50

Group: 2

Verdict: ACCEPTED

input
`2 25000 236383646331590 30973864010249...` view save

correct output
(empty)

user output
`70` view save

Test 51

Group: 2

Verdict: ACCEPTED

input
`2 25000 52783945537122 62819045853889 ...` view save

correct output
(empty)

user output
`70` view save

Test 52

Group: 2

Verdict: ACCEPTED

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

correct output
(empty)

user output
`70` view save

Test 53

Group: 2

Verdict: ACCEPTED

input
`2 100000 3977422187752 9172657585884 24...` view save

correct output
(empty)

user output
`70` view save

Test 54

Group: 2

Verdict: ACCEPTED

input
`2 100000 13262637344137 25327517069541 ...` view save

correct output
(empty)

user output
`70` view save

Test 55

Group: 2

Verdict: ACCEPTED

input
`2 100000 18832120122902 29507339632281 ...` view save

correct output
(empty)

user output
`70` view save

Test 56

Group: 2

Verdict: ACCEPTED

input
`2 100000 6181561812375 6378266039481 17...` view save

correct output
(empty)

user output
`70` view save

Test 57

Group: 2

Verdict: ACCEPTED

input
`2 100000 5829742 7847985 9866228 118844...` view save

correct output
(empty)

user output
`70` view save

Test 58

Group: 2

Verdict: ACCEPTED

input
`2 100000 535929232534 21492335528903 25...` view save

correct output
(empty)

user output
`70` view save

Test 59

Group: 2

Verdict: ACCEPTED

input
`2 100000 9057012105366 20678972320055 2...` view save

correct output
(empty)

user output
`70` view save

Test 60

Group: 2

Verdict: ACCEPTED

input
`2 100000 7697039304820 22564329077790 2...` view save

correct output
(empty)

user output
`70` view save

Test 61

Group: 2

Verdict: ACCEPTED

input
`2 100000 39366590558911 39585546629301 ...` view save

correct output
(empty)

user output
`70` view save

Test 62

Group: 2

Verdict: ACCEPTED

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

correct output
(empty)

user output
`70` view save

Test 63

Group: 2

Verdict: ACCEPTED

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

correct output
(empty)

user output
`70` view save

Test 64

Group: 2

Verdict: ACCEPTED

input
`2 118 1 500000000000000001 750000000...` view save

correct output
(empty)

user output
`70` view save

APIO 2016

Gap

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Test 38

Test 39

Test 40

Test 41

Test 42

Test 43

Test 44

Test 45

Test 46

Test 47

Test 48

Test 49

Test 50

Test 51

Test 52

Test 53

Test 54

Test 55

Test 56

Test 57

Test 58

Test 59

Test 60

Test 61

Test 62

Test 63

Test 64

Tasks

Submissions (Yytsi)