제출 #469677

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
469677		ymm	Gap (APIO16_gap)	C++17	30 / 100	816 ms	2868 KiB

gap

///
///   Let the voice of love take you higher!
///

#define _USE_MATH_DEFINES
#define FAST ios::sync_with_stdio(false),cin.tie(0);
#include <bits/stdc++.h>
#define Loop(x, l, r) for(int x = (l); x < (r); ++x)
#define LoopR(x, l, r) for(int x = (r)-1; x >= (l); --x)
#define all(x) x.begin(), x.end()
#define Kill(x) exit((cout << (x) << '\n', 0))
#define YN(flag) ((flag)? "YES": "NO")
#define F first
#define S second
typedef          long long   ll;
typedef unsigned long long  ull;
typedef std::pair<int,int>  pii;
typedef std::pair<ll ,ll >  pll;
using namespace std;

#include "gap.h"

/*ll N;
vector<ll> A;
int m1, m2;
void MinMax(ll s, ll t, ll* mn, ll* mx)
{
    int cnt = 0;
    *mn = *mx = -1;
    Loop(i,0,N)
    {
        if(s <= A[i] && A[i] <= t)
        {
            if(!cnt) *mn = A[i];
            *mx = A[i];
            ++cnt;
        }
    }
    m1 += 1;
    m2 += cnt+1;
}*/

tuple<ll,ll,ll> solve(ll l, ll r, ll ans)
{
    cerr << l << ' ' << r << '\n';
    if(r-l <= ans){
        ll mn, mx;
        MinMax(l,r,&mn,&mx);
        return {ans,mn,mx};
    }
    ll m = (l+r)/2;
    auto [ansl,mnl,mxl] = solve(l,m,ans);
    ans = max(ans, ansl);
    auto [ansr,mnr,mxr] = solve(m+1,r,ans);
    ans = max(ans, ansr);
    ans = max(ans, mnr-mxl);
    return {ans, mnl, mxr};
}

ll findGap(int t, int n)
{
    if(t==1)
    {
        vector<ll> a, b;
        ll l=0, r=1e18;
        Loop(_,0,n/2)
        {
            MinMax(l,r,&l,&r);
            a.push_back(l);
            b.push_back(r);
            ++l; --r;
        }
        if(n&1) MinMax(l,r,&l,&r), a.push_back(l);
        ll ans = 0;
        Loop(i,1,a.size()) ans = max(ans, a[i]-a[i-1]);
        Loop(i,1,b.size()) ans = max(ans, b[i-1]-b[i]);
        ans = max(ans, b.back()-a.back());
        return ans;
    }
    else
    {
        ll l=0, r=1e18;
        MinMax(l,r,&l,&r);
        ll ans = (r-l+n-2)/(n-1);
        return get<0>(solve(l,r,ans));
    }
}

/*int main()
{
    N = 5;
    A = {1, 2, 3, 5, 6};
    cout << findGap(2, N) << '\n';
    cout << m1 << ' ' << m2 << '\n';
}*/

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

gap.cpp: In function 'll findGap(int, int)':
gap.cpp:8:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define Loop(x, l, r) for(int x = (l); x < (r); ++x)
      |                                          ^
gap.cpp:75:9: note: in expansion of macro 'Loop'
   75 |         Loop(i,1,a.size()) ans = max(ans, a[i]-a[i-1]);
      |         ^~~~
gap.cpp:8:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define Loop(x, l, r) for(int x = (l); x < (r); ++x)
      |                                          ^
gap.cpp:76:9: note: in expansion of macro 'Loop'
   76 |         Loop(i,1,b.size()) ans = max(ans, b[i-1]-b[i]);
      |         ^~~~

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