Submission #152599

#	Time	Username	Problem	Language	Result	Execution time	Memory
152599		Ruxandra985	Gap (APIO16_gap)	C++14	100 / 100	79 ms	1916 KiB

gap

#include <cstdio>
#include "gap.h"


long long findGap (int t , int n){
    long long l,r,i;
    long long st,dr,a,b,sol,x,y,len,rant;
    if (t == 1){
        long long w[100010];
        st = 1;
        dr = 1000000000000000000;
        l = 1;
        r = n;
        while (l<=r){
            a=b=0;
            MinMax (st,dr,&a,&b);
            if (l < r){
                w[l] = a;
                w[r] = b;
            }
            else {
                w[l] = a;
            }
            st = a + 1;
            dr = b - 1;
            l++;
            r--;
        }
        sol = 0;
        for (i=2;i<=n;i++){
            if (sol < w[i] - w[i-1])
                sol = w[i] - w[i-1];
        }
        return sol;
    }
    else {
        MinMax (0,1000000000000000000,&a,&b);
      	if (n == 2)
          return b - a;
        len = (b - a - 2) / (n - 2);
        sol = 0;
        rant = a;
        /// imparti in n - 2 bucati , e clar ca exista bucati goale
        /// maximul se va obtine intre 2 elem consecutive din bucati dif
        for ( i = a+1 ; i < b ; i+=len ){
            MinMax (i , i + len - 1 , &l , &r);
            if (l != -1 && sol < l - rant){
                sol = l - rant;
               if (r + sol + 1 > b)
                    break;
            }
            if (r!=-1)
                rant = r;
        }

        return sol;
    }
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:7:29: warning: unused variable 'x' [-Wunused-variable]
     long long st,dr,a,b,sol,x,y,len,rant;
                             ^
gap.cpp:7:31: warning: unused variable 'y' [-Wunused-variable]
     long long st,dr,a,b,sol,x,y,len,rant;
                               ^

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70