Submission #406995

#	Time	Username	Problem	Language	Result	Execution time	Memory
406995		MKopchev	Shortcut (IOI16_shortcut)	C++14	71 / 100	2082 ms	2476 KiB

shortcut

#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;

const long long inf=1e18;

vector<long long> x={},add={};

int cut;

bool test(long long sz)
{
    long long sum_low=-inf,sum_high=inf;

    long long diff_low=-inf,diff_high=inf;

    for(int i=0;i<x.size();i++)
        for(int j=i+1;j<x.size();j++)
            if(add[i]+x[j]-x[i]+add[j]<=sz)continue;
            else
            {
                //cout<<"wrong "<<i<<" "<<j<<endl;

                long long RHS=sz-add[i]-add[j]-cut;

                //cout<<"sz= "<<sz<<" RHS= "<<RHS<<endl;

                if(RHS<0)return 0;

                sum_low=max(sum_low,x[i]+x[j]-RHS);

                sum_high=min(sum_high,x[i]+x[j]+RHS);

                diff_low=max(diff_low,-x[i]+x[j]-RHS);

                diff_high=min(diff_high,-x[i]+x[j]+RHS);
            }

    if(sum_low>sum_high)return 0;

    if(diff_low>diff_high)return 0;

    //cout<<"sz= "<<sz<<endl;

    //cout<<"sum: "<<sum_low<<" "<<sum_high<<" diff: "<<diff_low<<" "<<diff_high<<endl;

    for(int frst=0;frst<x.size();frst++)
    {
        long long low=max(sum_low-x[frst],diff_low+x[frst]);
        long long high=min(sum_high-x[frst],diff_high+x[frst]);

        //cout<<"low= "<<low<<" high= "<<high<<endl;

        if(low>high)continue;

        int pos=lower_bound(x.begin(),x.end(),low)-x.begin();

        if(pos<x.size()&&x[pos]<=high)return 1;
    }

    return 0;
}
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
    long long sum=0;

    x.push_back(0);

    for(auto w:l)
    {
        sum+=w;
        x.push_back(sum);
    }

    for(auto w:d)
        add.push_back(w);

    cut=c;

    long long ok=2e9+x.back();
    long long not_ok=-1;

    while(ok-not_ok>1)
    {
        long long av=(ok+not_ok)/2;

        if(test(av))ok=av;
        else not_ok=av;
    }

    return ok;
}
/*
int main()
{
    int n, c;
    assert(2 == scanf("%d%d", &n, &c));

    std::vector<int> l(n - 1);
    std::vector<int> d(n);
    for (int i = 0; i < n - 1; i++)
        assert(1 == scanf("%d", &l[i]));
    for (int i = 0; i < n; i++)
        assert(1 == scanf("%d", &d[i]));

    long long t = find_shortcut(n, l, d, c);


    printf("%lld\n", t);

    return 0;
}
*/

Compilation message (stderr)

shortcut.cpp: In function 'bool test(long long int)':
shortcut.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=0;i<x.size();i++)
      |                 ~^~~~~~~~~
shortcut.cpp:18:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for(int j=i+1;j<x.size();j++)
      |                       ~^~~~~~~~~
shortcut.cpp:47:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int frst=0;frst<x.size();frst++)
      |                    ~~~~^~~~~~~~~
shortcut.cpp:58:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         if(pos<x.size()&&x[pos]<=high)return 1;
      |            ~~~^~~~~~~~~

• 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