제출 #538300

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
538300		status_coding	Gap (APIO16_gap)	C++14	100 / 100	69 ms	3260 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>

using namespace std;

long long findGap(int t, int n)
{
    if(t == 1)
    {
        vector<long long> l, r;
        long long st=0, dr=1e18;

        while(n)
        {
            MinMax(st, dr, &st, &dr);

            if(st == dr)
            {
                l.push_back(st);
                break;

                n--;
            }

            l.push_back(st);
            r.push_back(dr);
            st++;
            dr--;

            n-=2;
        }

        while(!r.empty())
        {
            l.push_back(r.back());
            r.pop_back();
        }

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

        return ans;
    }
    else
    {
        long long st, dr;
        MinMax(0, 1e18, &st, &dr);

        long long x = (dr-st + n-2) / (n-1);
        vector<long long> v;

        v.push_back(st);
        st++;

        while(st < dr)
        {
            long long a, b;
            MinMax(st, st+x-1, &a, &b);

            if(a != -1)
            {
                v.push_back(a);
                v.push_back(b);
            }

            st+=x;
        }

        if(v.back() != dr)
            v.push_back(dr);

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

        return ans;
    }
}

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