oj.uz

답안 #745524

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
745524 2023-05-20T09:40:30 Z boris_mihov Shortcut (IOI16_shortcut) C++17
0 / 100
 1 ms 340 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 = 1e15;

int n, c;
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;
    }
};
 
int l[MAXN];
int d[MAXN];
int sortedPlus[MAXN];
int sortedMinus[MAXN];
llong p[MAXN];
 
bool check(llong allowed)
{
    Rectangle area;
    llong maxSub = -INF;
    int idxSum = 0;
    int idxSub = 0;
 
    for (int i = 1 ; i <= n ; ++i)
    {
        if (i > 1 && maxSub > allowed - d[i] - p[i])
        {
            area.low.y = std::max(area.low.y, p[i] + d[i] + maxSub + c - allowed);
            area.up.x = std::min(area.up.x, p[i] - d[i] - maxSub - c + allowed);
        }
 
        maxSub = std::max(maxSub, d[i] - p[i]);
    }
 
    int ptr = n + 1;
    llong maxSum = -INF;
    for (int i = 1 ; i <= n ; ++i)
    {
        if (sortedPlus[i] == 1)
        {
            continue;
        }

        while (ptr > 1 && p[sortedPlus[i]] + d[sortedPlus[i]] - p[sortedMinus[ptr - 1]] + d[sortedMinus[ptr - 1]] > allowed)
        {
            ptr--;
            maxSum = std::max(maxSum, p[sortedMinus[ptr]] + d[sortedMinus[ptr]]);  
        }
 
        if (ptr <= n)
        {
            area.low.x = std::max(area.low.x, p[sortedPlus[i]] + d[sortedPlus[i]] + maxSum + c - allowed);
            area.up.y = std::min(area.up.y, p[sortedPlus[i]] - d[sortedPlus[i]] - maxSum - c + allowed);
        }
    }
 
    ptr = 1;
    llong l, r;
    for (int i = n ; i >= 2 ; --i)
    {
        l = std::max(area.low.x - p[i], p[i] - area.up.y);
        r = std::min(area.up.x - p[i], p[i] - area.low.y);

        while (ptr < i && p[ptr] < l && p[ptr + 1] <= r)
        {
            ptr++;
        }
 
        if (ptr < i)
        {
            Point curr = {p[i] + p[ptr], p[i] - p[ptr]};
            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];
    }
 
    std::iota(sortedPlus + 1, sortedPlus + 1 + n, 1);
    std::iota(sortedMinus + 1, sortedMinus + 1 + n, 1);
    std::sort(sortedPlus + 1, sortedPlus + 1 + n, [&](int x, int y)
    {
        return d[x] + p[x] < d[y] + p[y];
    });
 
    std::sort(sortedMinus + 1, sortedMinus + 1 + n, [&](int x, int y)
    {
        return d[x] - p[x] < d[y] - p[y];
    });
 
    llong l = -1, r = INF, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (!check(mid)) l = mid;
        else r = mid;
    }
 
    return r;
}

Compilation message

shortcut.cpp: In function 'bool check(llong)':
shortcut.cpp:43:9: warning: unused variable 'idxSum' [-Wunused-variable]
   43 |     int idxSum = 0;
      |         ^~~~~~
shortcut.cpp:44:9: warning: unused variable 'idxSub' [-Wunused-variable]
   44 |     int idxSub = 0;
      |         ^~~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 7.0

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

Subtask #5
0 / 33.0

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

Subtask #6
0 / 22.0

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

Subtask #7
0 / 4.0

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

Subtask #8
0 / 3.0

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