Submission #476353

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
476353	2021-09-26T06:48:46 Z	ponytail	Gap (APIO16_gap)	C++17	100 / 100	56 ms	1948 KB

gap

#include "gap.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
 
long long findGap(int T, int N){
    long long arr[N];
    if(T==1){
        long long idx=0,mx,mn,l=0,r=1e18;
        for(int i=0;i<N/2+(N%2);i++){
            MinMax(l,r,&mn,&mx);
            arr[i]=mn;
            arr[N-i-1]=mx;
            l=mn+1;
            r=mx-1;
        }
    }
    else{
        long long idx=0,mx,mn,l=0,r=1e18;
        MinMax(l,r,&mn,&mx);
        l=mn;
        r=mx;
        long long extra=(r-l+N-2)/(N-1);
        for(long long i=l+1;i<r;){
            MinMax(i,i+extra-1,&mn,&mx);
            if(mx!=-1){
                i=mx+1;
                continue;
            }
            for(long long  j=2;;j++){
                MinMax(i,i+j*extra-1,&mn,&mx);
                if(mn!=-1){
                    extra=mn-i+1,i=mx+1;
                    break;
                }
            }
        }
        return extra;
    }
    long long ans=0;
    for(int i=0;i<N-1;i++)
        ans=max(ans,arr[i+1]-arr[i]);
    return ans;
}

Compilation message

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:9:19: warning: unused variable 'idx' [-Wunused-variable]
    9 |         long long idx=0,mx,mn,l=0,r=1e18;
      |                   ^~~
gap.cpp:19:19: warning: unused variable 'idx' [-Wunused-variable]
   19 |         long long idx=0,mx,mn,l=0,r=1e18;
      |                   ^~~

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	0 ms	200 KB	Output is correct
4	Correct	1 ms	200 KB	Output is correct
5	Correct	0 ms	200 KB	Output is correct
6	Correct	0 ms	200 KB	Output is correct
7	Correct	1 ms	200 KB	Output is correct
8	Correct	0 ms	200 KB	Output is correct
9	Correct	0 ms	200 KB	Output is correct
10	Correct	1 ms	200 KB	Output is correct
11	Correct	1 ms	328 KB	Output is correct
12	Correct	1 ms	328 KB	Output is correct
13	Correct	2 ms	328 KB	Output is correct
14	Correct	2 ms	328 KB	Output is correct
15	Correct	1 ms	328 KB	Output is correct
16	Correct	11 ms	668 KB	Output is correct
17	Correct	10 ms	584 KB	Output is correct
18	Correct	11 ms	604 KB	Output is correct
19	Correct	11 ms	584 KB	Output is correct
20	Correct	9 ms	700 KB	Output is correct
21	Correct	49 ms	1732 KB	Output is correct
22	Correct	43 ms	1732 KB	Output is correct
23	Correct	44 ms	1856 KB	Output is correct
24	Correct	42 ms	1820 KB	Output is correct
25	Correct	38 ms	1860 KB	Output is correct
26	Correct	41 ms	1868 KB	Output is correct
27	Correct	40 ms	1812 KB	Output is correct
28	Correct	44 ms	1856 KB	Output is correct
29	Correct	48 ms	1784 KB	Output is correct
30	Correct	37 ms	1856 KB	Output is correct
31	Correct	0 ms	200 KB	Output is correct
32	Correct	1 ms	304 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	0 ms	200 KB	Output is correct
4	Correct	1 ms	200 KB	Output is correct
5	Correct	0 ms	200 KB	Output is correct
6	Correct	0 ms	200 KB	Output is correct
7	Correct	0 ms	200 KB	Output is correct
8	Correct	0 ms	200 KB	Output is correct
9	Correct	0 ms	200 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	328 KB	Output is correct
12	Correct	1 ms	328 KB	Output is correct
13	Correct	1 ms	328 KB	Output is correct
14	Correct	1 ms	328 KB	Output is correct
15	Correct	1 ms	328 KB	Output is correct
16	Correct	7 ms	616 KB	Output is correct
17	Correct	9 ms	652 KB	Output is correct
18	Correct	7 ms	672 KB	Output is correct
19	Correct	10 ms	604 KB	Output is correct
20	Correct	6 ms	584 KB	Output is correct
21	Correct	27 ms	1856 KB	Output is correct
22	Correct	28 ms	1820 KB	Output is correct
23	Correct	38 ms	1804 KB	Output is correct
24	Correct	29 ms	1816 KB	Output is correct
25	Correct	56 ms	1948 KB	Output is correct
26	Correct	29 ms	1808 KB	Output is correct
27	Correct	27 ms	1840 KB	Output is correct
28	Correct	28 ms	1856 KB	Output is correct
29	Correct	27 ms	1816 KB	Output is correct
30	Correct	21 ms	1864 KB	Output is correct
31	Correct	0 ms	200 KB	Output is correct
32	Correct	0 ms	200 KB	Output is correct