Submission #1034281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034281		sleepntsheep	Text editor (CEOI24_editor)	C11	100 / 100	523 ms	35620 KiB

Main

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define N 1000000

int answer = 2e9;
int l[N];
int tt[N * 4], dp[N * 2], dp2[N * 2];
int n, sy, sx, ey, ex;

int mini(int i, int j) {
    return i < j ? i : j;
}
int ttmin(int i, int j) {
    return dp[i] < dp[j] ? i : j;
}
void pul(int i) {
    tt[i] = ttmin(tt[i * 2], tt[i * 2 + 1]);
}
void fix(int i) {
    for (i += 2 * n; i /= 2;)
        pul(i);
}

int main() {
    scanf("%d%d%d%d%d", &n, &sy, &sx, &ey, &ex);
    for (int i = 0; i < n; ++i)
        scanf("%d", l + i), ++l[i];
    --sy, --ey;

    /* 1st */
    {
        int basic = 0;
        int x, y;
        x = sx, y = sy;
        while (y != ey) {
            if (y < ey)
                ++y;
            else
                --y;
            ++basic;
            x = mini(x, l[y]);
        }
        basic += abs(x - ex);
        answer = basic;
    }

    /* 2nd */
    memset(dp, 63, sizeof dp);
    {
        int x = sx, y = sy, moves = 0;
        for (; y >= 0; --y) {
            x = mini(x, l[y]);
            if (dp[y * 2] > moves + (x - 1))
                dp[y * 2] = moves + x - 1;
            if (dp[y * 2 + 1] > moves + (l[y] - x))
                dp[y * 2 + 1] = moves + l[y] - x;
            ++moves;
        }
        x = sx, y = sy, moves = 0;
        for (; y < n; ++y) {
            x = mini(x, l[y]);
            if (dp[y * 2] > moves + (x - 1))
                dp[y * 2] = moves + x - 1;
            if (dp[y * 2 + 1] > moves + (l[y] - x))
                dp[y * 2 + 1] = moves + l[y] - x;
            ++moves;
        }
    }

    for (int i = 0; i < 2 * n; ++i)
        tt[i + 2 * n] = i;
    for (int i = 2 * n; --i;)
        pul(i);

    /* dijkstra */
    for (int i = 0; i < 2 * n; ++i) {
        int u = tt[1];
        int cost = dp[u];
        dp2[u] = cost + 1;
        dp[u] = 2e9;
        fix(u);

        if (0 == dp2[u ^ 1] && dp[u ^ 1] > cost + l[u / 2] - 1) {
            dp[u ^ 1] = cost + l[u / 2] - 1;
            fix(u ^ 1);
        }

        if ((u & 1) && (u / 2) + 1 < n && !dp2[u + 1] && dp[u + 1] > cost + 1) {
            dp[u + 1] = cost + 1;
            fix(u + 1);
        }

        if (!(u & 1) && u && !dp2[u - 1] && dp[u - 1] > cost + 1) {
            dp[u - 1] = cost + 1;
            fix(u - 1);
        }

        if (u & 1) {
            if (u - 2 >= 0 && !dp2[u - 2] && l[u / 2] >= l[u / 2 - 1] && dp[u - 2] > cost + 1) {
                dp[u - 2] = cost + 1;
                fix(u - 2);
            }
            if (u + 2 < 2 * n && !dp2[u + 2] && l[u / 2] >= l[u / 2 + 1] && dp[u + 2] > cost + 1) {
                dp[u + 2] = cost + 1;
                fix(u + 2);
            }
        } else {
            if (u - 2 >= 0 && !dp2[u - 2] && dp[u - 2] > cost + 1) {
                dp[u - 2] = cost + 1;
                fix(u - 2);
            }
            if (u + 2 < 2 * n && !dp2[u + 2] && dp[u + 2] > cost + 1) {
                dp[u + 2] = cost + 1;
                fix(u + 2);
            }
        }
    }

    {
        int y, leftest;
        y = ey, leftest = l[ey];
        for (; y >= 0; --y) {
            if (l[y] <= leftest)
                answer = mini(answer, ey - y + abs(ex - l[y]) + dp2[y * 2 + 1] - 1);
            leftest = mini(leftest, l[y]);
        }
        y = ey, leftest = l[ey];
        for (; y < n; ++y) {
            if (l[y] <= leftest)
                answer = mini(answer, y - ey + abs(ex - l[y]) + dp2[y * 2 + 1] - 1);
            leftest = mini(leftest, l[y]);
        }
    }

    answer = mini(answer, mini(-1+ex -1 + dp2[ey * 2], - 1+  dp2[ey * 2 + 1] + l[ey] - ex));

    printf("%d\n", answer);
    return 0;
}

/*
 *
 *
 * first option - travel without using line-changing horizontal move
 * second option - use line-changing horizontal
 *      - dijkstra where each line is 2 node (start, end)
 */

Compilation message (stderr)

Main.c: In function 'main':
Main.c:27:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     scanf("%d%d%d%d%d", &n, &sy, &sx, &ey, &ex);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:29:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         scanf("%d", l + i), ++l[i];
      |         ^~~~~~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 26 / 26
• Subtask 4: 11 / 11
• Subtask 5: 44 / 44