Submission #745443

#	Time	Username	Problem	Language	Result	Execution time	Memory
745443		boris_mihov	Shortcut (IOI16_shortcut)	C++17	0 / 100	1 ms	340 KiB

shortcut

#include "shortcut.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXN = 1000000 + 10;
const llong INF = 1e16;

struct Point
{
    llong x, y;
};

struct Rectangle
{
    Point low, up;
    Rectangle()
    {
        low.x = low.y = -INF;
        up.x = up.y = INF;
    }

    bool isInside(Point p)
    {
        return low.x <= p.x && low.y <= p.y && low.x <= up.x && low.y <= up.y;
    }
};

bool haveIntersection(Rectangle a, Rectangle b)
{
    return !(a.up.x < b.low.x || b.up.x < a.low.x || a.up.y < b.low.y || b.up.y < a.low.y); 
}

Rectangle intersect(Rectangle a, Rectangle b)
{
    Rectangle res;
    res.low.x = std::max(a.low.x, b.low.x);
    res.low.y = std::max(a.low.y, b.low.y);
    res.up.x = std::min(a.up.x, b.up.x);
    res.up.y = std::min(a.up.y, b.up.y);
    return res;
}

int n, c;
int l[MAXN];
int d[MAXN];
llong p[MAXN];

bool check(llong allowed)
{
    Rectangle area;
    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = i + 1 ; j <= n ; ++j)
        {
            if (p[j] - p[i] + d[i] + d[j] <= allowed)
            {
                continue;
            }

            if (allowed < 1LL * c + d[i] + d[j])
            {
                return false;
            }

            Point centre = {p[j] + p[i], p[j] - p[i]};
            Rectangle curr;

            curr.low.x = centre.x - (allowed - c - d[i] - d[j]);
            curr.low.y = centre.y - (allowed - c - d[i] - d[j]);
            curr.up.x = centre.x + (allowed - c - d[i] - d[j]);
            curr.up.y = centre.y + (allowed - c - d[i] - d[j]);

            if (!haveIntersection(area, curr))
            {
                return false;
            }

            area = intersect(area, curr);
        }
    }
    
    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = i + 1 ; j <= n ; ++j)
        {
            Point curr = {p[j] + p[i], p[j] - p[i]};
            if (area.isInside(curr))
            {
                return true;
            }
        }
    }

    return false;
}

llong find_shortcut(int N, std::vector <int> L, std::vector <int> D, int C)
{
    n = N; c = C;
    for (int i = 0 ; i < n - 1 ; ++i)
    {
        l[i + 1] = L[i]; 
    }

    for (int i = 0 ; i < n ; ++i)
    {
        d[i + 1] = D[i];
    }

    p[1] = 0;
    for (int i = 2 ; i <= n ; ++i)
    {
        p[i] = p[i - 1] + l[i - 1];
    }

    llong l = -1, r = INF, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (!check(mid)) l = mid;
        else r = mid;
    }

    return r;
}

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