oj.uz

Submission #407004

# Submission time Handle Problem Language Result Execution time Memory
407004 2021-05-18T10:14:19 Z MKopchev Shortcut (IOI16_shortcut) C++14
0 / 100
 1 ms 204 KB 
#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;

const long long inf=1e18;

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

void push(long long sum,int d)
{
    while(x.size())
    {
        if(add.back()+sum-x.back()<=d)
        {
            add.pop_back();
            x.pop_back();
            continue;
        }
        else if(sum-x.back()+d<=add.back())return;
        else break;
    }

    x.push_back(sum);
    add.push_back(d);
}
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;

    push(0,d[0]);

    for(int i=0;i<l.size();i++)
    {
        sum+=l[i];

        push(sum,d[i+1]);
    }

    //cout<<x.size()<<endl;

    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

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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 204 KB n = 2, incorrect answer: jury 62 vs contestant 0
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 204 KB n = 2, incorrect answer: jury 62 vs contestant 0
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 204 KB n = 2, incorrect answer: jury 62 vs contestant 0
6 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 204 KB n = 2, incorrect answer: jury 62 vs contestant 0
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 204 KB n = 2, incorrect answer: jury 62 vs contestant 0
6 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 204 KB n = 2, incorrect answer: jury 62 vs contestant 0
6 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 204 KB n = 2, incorrect answer: jury 62 vs contestant 0
6 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 204 KB n = 2, incorrect answer: jury 62 vs contestant 0
6 Halted 0 ms 0 KB -