Submission #646375

#	Time	Username	Problem	Language	Result	Execution time	Memory
646375		Tenis0206	Gap (APIO16_gap)	C++11	30 / 100	861 ms	524288 KiB

gap

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

using namespace std;

long long n;

long long bck = 1000;
int pmax = 0;

struct nod
{
    long long val,Min,Max;
};

long long solve1()
{
    int l = 1;
    int r = n;
    long long st = 0, dr = 1e18;
    vector<long long> a,b;
    while(l<=r)
    {
        long long x,y;
        MinMax(st,dr,&x,&y);
        a.push_back(x);
        b.push_back(y);
        ++l;
        --r;
        st = x + 1;
        dr = y - 1;
    }
    vector<long long> v;
    for(auto it : a)
    {
        v.push_back(it);
    }
    reverse(b.begin(),b.end());
    for(auto it : b)
    {
        v.push_back(it);
    }
    long long Max = 0;
    for(int i=1;i<v.size();i++)
    {
        Max = max(Max,v[i] - v[i-1]);
    }
    return Max;
}

nod divide2(long long st, long long dr)
{
    if(st > dr)
    {
        return nod{-1,-1,-1};
    }
    long long x,y;
    MinMax(st,dr,&x,&y);
    if(x==-1)
    {
        return nod{-1,-1,-1};
    }
    if(x==y)
    {
        return nod{-1,x,y};
    }
    if(st==1 && dr==1e18)
    {
        pmax = (y - x + n) / (n - 1);
    }
    st = x, dr = y;
    if(dr - st + 1 <= pmax)
    {
        return nod{-1,x,y};
    }
    long long last = st - 1;
    long long rez = -1;
    long long Max = -1;
    for(int i=1;i<=bck;i++)
    {
        long long mij = st + ((dr - st) / bck) * i;
        if(i==bck)
        {
            mij = dr;
        }
        if(Max!=-1)
        {
            last = Max;
        }
        nod son = divide2(last+1,mij);
        last = mij;
        rez = max(rez,son.val);
        if(Max!=-1 && son.Min!=-1)
        {
            rez = max(rez,son.Min - Max);
        }
        if(son.Max!=-1)
        {
            Max = son.Max;
        }
        if(mij==dr)
        {
            break;
        }
    }
    return nod{rez,x,y};
}

long long findGap(int t, int N)
{
    n = N;
    if(t==1)
    {
        return solve1();
    }
    bck = min(bck,n/2);
    return divide2(1,1e18).val;
}

Compilation message (stderr)

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

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