제출 #125938

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
125938		kjp4155	Gap (APIO16_gap)	C++17	30 / 100	75 ms	4716 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
ll MX = 1e18;
ll A[500500];
 
ll findGap1(int N){
    int L=1, R=N;
    ll mn = 0, mx = MX;
    while( L <= R ){
        ll a,b;
        MinMax(mn, mx, &a, &b);
        A[L++] = a; A[R--] = b;
        mn = a + 1; mx = b-1;
    }
 
    ll ans = 0;
    for(int i=1;i<N;i++) ans = max(ans, A[i+1]-A[i]);
 
    return ans;
}
 
ll findGap2(int N){
    ll L = 0, R = 1e18;
    MinMax(L, R, &L, &R);

    ll gap = (R-L+(N-1))/(N-2);
    ll ans = gap;

    vector<ll> v;
    v.push_back(L);
    for(ll i=L;i<R;i+=gap){
        ll l,r; MinMax(i, i+gap, &l, &r);
        if( l != -1 ) v.push_back(l);
        if( r != -1 ) v.push_back(r);
    }

    v.push_back(R);


    for(int i=0;i<v.size()-1;i++) ans = max(ans, v[i+1]-v[i]);

    return ans;
}
 
long long findGap(int T, int N){
    if( T == 1 ) return findGap1(N);
    else return findGap2(N);
}

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

gap.cpp: In function 'll findGap2(int)':
gap.cpp:44:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v.size()-1;i++) ans = max(ans, v[i+1]-v[i]);
                 ~^~~~~~~~~~~

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