제출 #1009630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1009630		dpsaveslives	Gap (APIO16_gap)	C++17	100 / 100	46 ms	3624 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF = 1e18;
ll findGap(int T, int N){
    if(T == 1){
        ll l = 1, r = INF;
        ll mn, mx;
        vector<ll> arr(N);
        int ind = 0;
        for(int i = 1;i<=(N+1)/2;++i){
            MinMax(l,r,&mn,&mx);
            arr[ind] = mn;
            arr[++ind] = mx;
            ++ind;
            l = mn+1; r = mx-1;
        }
        sort(arr.begin(),arr.end());
        ll ans = 0;
        for(int i = 0;i<=arr.size()-1;++i){
            ans = max(ans,arr[i+1]-arr[i]);
        }
        return ans;
    }
    ll a1, an;
    MinMax(1,INF,&a1,&an);
    ll k = (an-a1+N-2)/(N-1); //N-1 differences between i and i+1
    ll cur = a1,x,y,ans = k, last = a1;
    while(cur+k+1 <= an){
        MinMax(cur,cur+k,&x,&y);
        if(x != -1){
            ans = max(ans,x-last);
            last = y;
        }
        cur += k+1;
    }
    MinMax(cur,an,&x,&y);
    if(x != -1){
        ans = max(ans,x-last);
    }
    return ans;
}

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

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:21:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for(int i = 0;i<=arr.size()-1;++i){
      |                       ~^~~~~~~~~~~~~~

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