Submission #152583

#	Time	Username	Problem	Language	Result	Execution time	Memory
152583		Ruxandra985	Gap (APIO16_gap)	C++14	42.65 / 100	71 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,mid,last;
    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);
        l = a;
        r = b;
        sol = 1;
        while (l <= b && b - l > sol){ /// daca dif e mai mica , irelevant
            /// as vrea sa trec in urmatorul la o distanta > sol
            MinMax (l+1 , l + sol , &x , &y);
            if (x!=-1){ /// exista ceva , skip
                l = y;
            }
            else { /// e doar l
                st = sol + 1;
                dr = b - l;
                while (st<=dr){
                    mid = (st + dr)/2;
                    MinMax (l+1 , l + mid , &x , &y);
                    if (y == -1){ /// vreau mai mare , la M s a adunat 1
                        st = mid + 1;
                    }
                    else {
                        last = x;
                        break;
                    }
                }
                sol = last - l;
                l = last;
            }
        }

        return sol;
    }
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:59:21: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 sol = last - l;
                 ~~~~^~~~~~~~~~

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