제출 #625940

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
625940		socpite	Gap (APIO16_gap)	C++14	100 / 100	56 ms	3204 KiB

gap

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

#define f first
#define s second

typedef long long ll;


long long findGap(int T, int N)
{
    ll l, r, ans = 0, n = N;
    MinMax(0, 1e18, &l, &r);
    if(T==1){
        for(int i = 0; i < (n-1)/2; i++){
            ll nxtl, nxtr;
            MinMax(l+1, r-1, &nxtl, &nxtr);
            ans = max(ans, nxtl-l);
            ans = max(ans, r-nxtr);
            l = nxtl;
            r = nxtr;
        }
        ans = max(ans, r-l);
    }
    else{
        vector<pair<ll, ll>> vec;
        ll dist = (r-l-1)/n + !!((r-l-1)%n);
        for(ll i = l+1; i < r; i+=dist){
            ll rb = min(r-1, i+dist-1);
            pair<ll, ll> tmp;
            MinMax(i, rb, &tmp.f, &tmp.s);
            if(tmp.f >= 0)vec.push_back(tmp);
        }
        if(vec.empty())ans = r-l;
        else{
            ans = max(vec[0].f - l, r-vec.back().s);
            for(int i = 1; i < vec.size(); i++){
                ans = max(ans, vec[i].f - vec[i-1].s);
            }
        }
    }
    return ans;
}

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

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

• 서브태스크 1: 30 / 30
• 서브태스크 2: 70 / 70