제출 #95786

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
95786		dantoh000	Gap (APIO16_gap)	C++14	100 / 100	153 ms	3952 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"
using namespace std;


long long findGap(int T, int n)
{
    if (T == 1){
        long long a[n];
        int cur = 0;
        MinMax(0,1000000000000000000,a,a+n-1);
        cur++;
        while (cur < (n+1)/2){
            //printf("%d ",cur);
            MinMax(a[cur-1]+1,a[n-cur]-1,a+cur,a+n-1-cur);
            cur++;
        }
        long long ans = 0;
        for (int i = 1; i < n; i++){
            //printf("%lld %lld, ",a[i],a[i-1]);
            ans = max(ans,a[i]-a[i-1]);
        }
        return ans;
    }
    else{
        long long lo, hi;
        MinMax(0ll,1000000000000000000ll,&lo,&hi);
        long long diff = (hi-lo)/(n-1) + ((hi-lo)%(n-1)!=0);
        //printf("%lld ",diff);
        vector<long long> v;
        v.push_back(lo);
        long long qs = lo+1, qe = lo+diff;
        long long a,b;
        for (int i = 0; i < n; i++){
            //printf("query %lld %lld\n",qs,qe);
            MinMax(qs,qe,&a,&b);
            qs += diff;
            qe += diff;
            if (a == -1 && b == -1) continue;
            v.push_back(a);
            if (b != a) v.push_back(b);

        }
        v.push_back(hi);
        long long ans = 0;
        for (int i = 1; i < v.size(); i++){
            ans = max(v[i]-v[i-1],ans);
        }
        return ans;
    }
}

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

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:46:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 1; i < v.size(); i++){
                         ~~^~~~~~~~~~

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