oj.uz

Submission #225356

# Submission time Handle Problem Language Result Execution time Memory
225356 2020-04-20T11:14:14 Z VEGAnn Shortcut (IOI16_shortcut) C++14
0 / 100
 5 ms 256 KB 
#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;
typedef long long ll;
const int N = 3010;
const ll OO = 1e18;
ll pf[N], dst[N], c;
int n;

bool ok(ll mx){
    bool was = 0;
    ll u = -1, d = -1, l = -1, r = -1;

    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++)
            if (pf[j] - pf[i] + dst[j] + dst[i] > mx){
                ll k = mx - dst[i] - dst[j] - c;
                if (k < 0) return 0;

                ll up = pf[j] + k, down = pf[j] - k;
                ll lft = pf[i] - k, rgt = pf[i] + k;

                ll cu = up + pf[i];
                ll cd = down + pf[i];
                ll cl = pf[i] - up / 2;
                ll cr = pf[i] - down / 2;

                if (!was){
                    was = 1;
                    u = cu; d = cd; l = cl; r = cr;
                } else {
                    u = min(u, cu);
                    d = max(d, cd);
                    if (u < d) return 0;
                    l = max(l, cl);
                    r = min(r, cr);
                    if (r < l) return 0;
                }
            }

    if (!was) return 1;

    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++){
            ll up = pf[j], down = pf[j];
            ll lft = pf[i], rgt = pf[i];

            ll cu = up + pf[i];
            ll cd = down + pf[i];
            ll cl = pf[i] - up / 2;
            ll cr = pf[i] - down / 2;

            cu = min(u, cu);
            cd = max(d, cd);
            if (cu < cd) continue;

            cl = max(l, cl);
            cr = min(r, cr);
            if (cr < cl) continue;

            return 1;
        }

    return 0;
}

long long find_shortcut(int N, std::vector<int> l, std::vector<int> d, int C){
    n = N;
    c = C * 2;

    assert(n <= 3000);

    pf[0] = 0;

    for (int i = 0; i < n - 1; i++) {
        pf[i + 1] = pf[i] + l[i] * 2;
        dst[i] = d[i] * 2;
    }

    dst[n - 1] = d[n - 1] * 2;

    // smth smaller
    ll l1 = 0, r1 = OO;

    while (l1 < r1){
        ll md = (l1 + r1) >> 1;

        if (ok(md))
            r1 = md;
        else l1 = md + 1;
    }

    return l1 / 2;
}

Compilation message

shortcut.cpp: In function 'bool ok(ll)':
shortcut.cpp:21:20: warning: unused variable 'lft' [-Wunused-variable]
                 ll lft = pf[i] - k, rgt = pf[i] + k;
                    ^~~
shortcut.cpp:21:37: warning: unused variable 'rgt' [-Wunused-variable]
                 ll lft = pf[i] - k, rgt = pf[i] + k;
                                     ^~~
shortcut.cpp:46:16: warning: unused variable 'lft' [-Wunused-variable]
             ll lft = pf[i], rgt = pf[i];
                ^~~
shortcut.cpp:46:29: warning: unused variable 'rgt' [-Wunused-variable]
             ll lft = pf[i], rgt = pf[i];
                             ^~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 7.0

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

Subtask #5
0 / 33.0

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

Subtask #6
0 / 22.0

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

Subtask #7
0 / 4.0

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

Subtask #8
0 / 3.0

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