oj.uz

답안 #745478

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
745478 2023-05-20T08:07:42 Z boris_mihov Shortcut (IOI16_shortcut) C++17
0 / 100
 1 ms 308 KB 
#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 && p.x <= up.x && p.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 = 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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 308 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 308 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 308 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 308 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 308 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 308 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 308 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 308 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -