Submission #886437

#	Time	Username	Problem	Language	Result	Execution time	Memory
886437		HuyQuang_re_Zero	Shortcut (IOI16_shortcut)	C++14	71 / 100	2063 ms	11868 KiB

shortcut

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define IDB pair <db,int>
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
using namespace std;
#include "shortcut.h"
ll n,c,i,j,u,v,x[1000005],h[1000005],tight1,tight2,tight3,tight4;
II sum[1000005],sub[1000005];
const ll oo=round(1e18);
ll Add_edge(int u,int v)
{
    ll res=0;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            res=max(res,min(x[j]-x[i],abs(x[i]-x[u])+abs(x[j]-x[v])+c)+h[i]+h[j]);
    return res;
}
bool check(ll k)
{
    if(k==tight3) return 1;
    tight1=tight2=-1e18;
    for(i=1;i<=n;i++)
    {
        j=n-(sum[n].snd==sub[i].snd);
        if(h[sum[j].snd]+x[sum[j].snd]+h[sub[i].snd]-x[sub[i].snd]<=k) continue;
        tight1=max(tight1,h[sum[j].snd]+x[sum[j].snd]+h[sub[i].snd]+x[sub[i].snd]);
    }
    for(j=1;j<=n;j++)
    {
        i=n-(sub[n].snd==sum[j].snd);
        if(h[sum[j].snd]+x[sum[j].snd]+h[sub[i].snd]-x[sub[i].snd]<=k) continue;
        tight2=max(tight2,h[sum[j].snd]-x[sum[j].snd]+h[sub[i].snd]-x[sub[i].snd]);
    }
    ll l=n+1,r=0,opt=oo;
    for(i=1;i<=n;i++)
    {
        while(l>1 && x[l-1]>=-x[i]-k+c+tight1) l--;
        while(r<n && x[r+1]<=min(k-c-tight2-x[i],k-c-tight3+x[i])) r++;
        while(r>0 && x[r]>min(k-c-tight2-x[i],k-c-tight3+x[i])) r--;
        if(l>r || l>i) continue;
        ll j=min(r,i);
      //  cerr<<(x[j]<=-x[i]-k+c+tight1)<<'\n';
    //    cerr<<(x[j]<=min(k-c-tight2-x[i],k-c-tight3+x[i]))<<'\n';
        if(opt>x[i]-x[j])
        {
            opt=x[i]-x[j];
            u=j; v=i;
        }
    }
    if(opt==oo) return 0;
    return Add_edge(u,v)<=k;
}
ll find_shortcut(int _n,vector <int> len,vector <int> d,int _c)
{
    n=_n; c=_c;
    ll dis=0;
    for(i=0;i<len.size();i++) x[i+1]=dis,dis+=len[i];
    x[n]=dis;
    for(i=0;i<d.size();i++) h[i+1]=d[i];
    for(i=1;i<=n;i++) sum[i]={ h[i]+x[i],i },sub[i]={ h[i]-x[i],i };
    sort(sum+1,sum+n+1);
    sort(sub+1,sub+n+1);
    ll ma=-1e18;
    for(i=1;i<=n;i++)
    {
        tight3=max(tight3,h[i]+x[i]+ma);
        ma=max(ma,h[i]-x[i]);
    }
  //  check(10992); exit(0);
    ll l=0,r=tight3;
    while(l<r)
    {
        ll mid=(l+r)>>1;
        if(check(mid)) r=mid; else l=mid+1;
    }
    return l;
}
/*
int main()
{
    freopen("shortcut.inp","r",stdin);
    freopen("shortcut.out","w",stdout);
    int n,c,x;
    vector <int> l,d;
    cin>>n>>c;
    for(i=1;i<n;i++) cin>>x,l.push_back(x);
    for(i=1;i<=n;i++) cin>>x,d.push_back(x);
    cout<<find_shortcut(n,l,d,c);
}

*/

Compilation message (stderr)

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:69:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(i=0;i<len.size();i++) x[i+1]=dis,dis+=len[i];
      |             ~^~~~~~~~~~~
shortcut.cpp:71:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(i=0;i<d.size();i++) h[i+1]=d[i];
      |             ~^~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 33 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3