Submission #569179

#	Time	Username	Problem	Language	Result	Execution time	Memory
569179		Deepesson	Gap (APIO16_gap)	C++17	100 / 100	75 ms	8508 KiB

gap

#include <bits/stdc++.h>

#include "gap.h"

void MinMax(long long, long long, long long*, long long*);

using ll = long long;
const ll left = 0,right = 1e18;
long long findGap(int T, int N)
{
    if(T==1)
     {
        std::map<ll,bool> mapa;
        ll l=-1,r=1e18;++r;
        while(mapa.size()!=N){
            ll a,b;
            if(l+1>r-1)break;
            MinMax(l+1,r-1,&a,&b);
            if(a!=-1){
                mapa[a]=true;
                l=a;
            }
            if(b!=-1){
                mapa[b]=true;
                r=b;
            }
            if(a==b&&a==-1)break;
        }
        ll max=0;
        std::vector<ll> vec;
        std::sort(vec.begin(),vec.end());
        for(auto&x:mapa)vec.push_back(x.first);
        for(int i=1;i!=vec.size();++i)max=std::max(max,vec[i]-vec[i-1]);
        return max;
    }
    else {
        ll a,b;
        MinMax(left,right,&a,&b);
        if(N==2)return b-a;

        ll falta = ((b-1)-(a+1)+1);
        ll ops = 3*N;
        ops-=N+1;
        ops-=N-2;
        ll cada = falta/ops;
        ll bonus = falta%ops;
        ll start = a+1;
        ll prev=a;
        ll ans=0;
        for(int i=0;i!=ops;++i){
            ll anda = cada;
            if(bonus){
                ++anda;
                --bonus;
            }
            ll end = start+anda-1;
            ll x,y;
            MinMax(start,end,&x,&y);
            if(x!=-1){
                ans=std::max(ans,x-prev);
                prev=y;
            }
            start=end+1;
        }
        ans=std::max(ans,b-prev);
        return ans;
    }
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:15:26: warning: comparison of integer expressions of different signedness: 'std::map<long long int, bool>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   15 |         while(mapa.size()!=N){
      |               ~~~~~~~~~~~^~~
gap.cpp:33:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for(int i=1;i!=vec.size();++i)max=std::max(max,vec[i]-vec[i-1]);
      |                     ~^~~~~~~~~~~~

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