제출 #152572

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
152572		Ruxandra985	Gap (APIO16_gap)	C++14	33.34 / 100	71 ms	3728 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 = 0;
        while (l <= b && b - l > sol){ /// daca dif e mai mica , irelevant
            /// as vrea sa trec in urmatorul la o distanta > sol
            MinMax (l , l + sol , &x , &y);
            if (x < y){ /// exista ceva , skip
                l = y;
            }
            else { /// e doar l
                st = sol + 1;
                dr = b - l;
                while (st<=dr){
                    mid = (st + dr)/2;
                    MinMax (l , l + mid , &x , &y);
                    if (y == l){ /// vreau mai mare
                        st = mid + 1;
                    }
                    else {
                        last = y;
                        dr = y - l - 1;
                    }
                }
                sol = last - l;
                l = last;
            }
        }

        return sol;
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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

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