Submission #1071770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071770		jer033	Text editor (CEOI24_editor)	C++17	30 / 100	916 ms	387492 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using tlii = tuple<ll, int, int>;
using tiii = tuple<int, int, int>;
using pii = pair<int, int>;
const int INF = 2'001'111'111;

ll nocheat(ll a, ll b, ll c, ll d)
{
    return abs(a-c)+abs(b-d);
}

ll switc(ll a, ll b)
{
    //a is from the left, b is from the right
    if (b<a)
        return a-b;
    else
        return b-a+2ll;
}

int main()
{
    std::ios::sync_with_stdio(false);
    int N;
    cin >> N;
    int sl, sc, el, ec;
    cin >> sl >> sc >> el >> ec;
    vector<int> width(N+1, 0);
    bool st2 = 0;
    if (N<=1000)
        st2 = 1;
    for (int i=1; i<=N; i++)
    {
        cin >> width[i];
        if (width[i]>5000)
            st2 = 0;
    }
    if (N<=2)
    {
        if ((sl==el) and (sc==ec))
            cout << "0\n";
        else if (el==2)
            cout << "1\n";
        else if (sl==2)
            cout << 1+min(ec-1, width[1]+1-ec) << '\n';
        else
            cout << min(abs(sc-ec), 2+min(ec-1, width[1]+1-ec)) << '\n';
    }
    else if (st2)
    {
        vector<vector<vector<pii>>> edges(N+1);
        vector<vector<int>> dists(N+1);
        for (int i=1; i<=N; i++)
        {
            int maxj = 1+width[i];
            edges[i].push_back({});
            dists[i].push_back(INF);
            for (int j=1; j<=maxj; j++)
            {
                vector<pii> edg;
                //go left
                if (j!=1)
                    edg.push_back({i, j-1});
                else if (i!=1)
                    edg.push_back({i-1, 1+width[i-1]});

                //go right
                if (j!=maxj)
                    edg.push_back({i, j+1});
                else if (i!=N)
                    edg.push_back({i+1, 1});

                //go up
                if (i!=1)
                    edg.push_back({i-1, min(j, 1+width[i-1])});

                //go down
                if (i!=N)
                    edg.push_back({i+1, min(j, 1+width[i+1])});
                
                edges[i].push_back(edg);
                dists[i].push_back(INF);
            }
        }
        queue<pii> visitlist;
        visitlist.push({sl, sc});
        dists[sl][sc] = 0;
        while (!visitlist.empty())
        {
            pii kk = visitlist.front();
            visitlist.pop();
            int k1 = kk.first;
            int k2 = kk.second;
            for (pii qq: edges[k1][k2])
            {
                int q1 = qq.first;
                int q2 = qq.second;
                if (dists[q1][q2] == INF)
                {
                    dists[q1][q2] = dists[k1][k2]+1;
                    visitlist.push({q1, q2});
                }
            }
        }
        cout << dists[el][ec] << '\n';
    }
    else
    {
        ll conwidth = width[1];
        ll a, b, c, d, n;
        n = N;
        a = sl;
        b = sc;
        c = el;
        d = ec;
        ll mindist = nocheat(a, b, c, d);

        //cheat through the last row
        ll las = 1+min(nocheat(n-1, 1, c, d), nocheat(n-1, conwidth+1, c, d));
        if (c == n)
            las = 0;
        ll las_cost = las+(n-a);
        mindist = min(mindist, las_cost);

        //cheat elsewhere
        ll sleft = b-1;
        ll sright = conwidth+1-b;
        ll eleft = d-1;
        ll eright = conwidth+1-d;
        mindist = min(mindist, sleft+eleft+abs(a-c));
        mindist = min(mindist, sright+eright+abs(a-c));
        mindist = min(mindist, sleft+eright+switc(a, c));
        mindist = min(mindist, eleft+sright+switc(c, a));

        cout << mindist << '\n';
    }
}

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