Submission #1214308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214308		spetr	Text editor (CEOI24_editor)	C++20	14 / 100	2133 ms	1114112 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mmod = 998244353;
#define vl vector<ll>
#define vint vector<vector<ll>>

ll powmod(ll x, ll n, ll mod){
    if (n == 0) return 1;
    ll half = powmod(x, n / 2, mod);
    ll half_sq = (half * half) % mod;
    return (n % 2 == 0 ? half_sq : (half_sq * x) % mod);
}

ll inversion_x(ll x, ll m){
    return powmod(x, m-2, mmod);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    ll n;
    ll sx, sy, ex, ey;
    cin >> n >> sy >> sx >> ey >> ex;

    vl lines(n);
    for(ll i = 0; i < n; i++){
        cin >> lines[i];
    }

    auto encode = [&](ll x, ll y) {
        return (y << 32) | x;
    };

    queue<vl> fronta;
    fronta.push({sx-1, sy-1, 0});
    unordered_set<ll> visited;

    if (sx == ex && sy == ey) {
        cout << 0;
        return 0;
    }

    vint dirs {{1,0},{-1,0},{0,1},{0,-1}};
    while (!fronta.empty()){
        vl prvek = fronta.front(); fronta.pop();
        ll x = prvek[0], y = prvek[1], dist = prvek[2];

        if (x == ex-1 && y == ey-1){
            cout << dist;
            break;
        }

        // 4 směry: vlevo, vpravo, nahoru, dolu
        // Move left
        {
            ll nx = x, ny = y;
            if (x > 0) {
                nx = x - 1;
            } else if (x == 0 && y > 0) {
                ny = y - 1; nx = lines[ny];
            } else {
                nx = -1;
            }
            if (nx >= 0) {
                ll code = encode(nx, ny);
                if (!visited.count(code)) {
                    if (nx == ex-1 && ny == ey-1) {
                        cout << dist + 1;
                        return 0;
                    }
                    visited.insert(code);
                    fronta.push({nx, ny, dist + 1});
                }
            }
        }

        // Move right
        {
            ll nx = x, ny = y;
            if (x < lines[y]) {
                nx = x + 1;
            } else if (x == lines[y] && y < n - 1) {
                ny = y + 1; nx = 0;
            } else {
                nx = -1;
            }
            if (nx >= 0) {
                ll code = encode(nx, ny);
                if (!visited.count(code)) {
                    if (nx == ex-1 && ny == ey-1) {
                        cout << dist + 1;
                        return 0;
                    }
                    visited.insert(code);
                    fronta.push({nx, ny, dist + 1});
                }
            }
        }

        // Move up
        if (y > 0) {
            ll ny = y - 1;
            ll nx = min(x, lines[ny]);
            ll code = encode(nx, ny);
            if (!visited.count(code)) {
                if (nx == ex-1 && ny == ey-1) {
                    cout << dist + 1;
                    return 0;
                }
                visited.insert(code);
                fronta.push({nx, ny, dist + 1});
            }
        }

        // Move down
        if (y < n - 1) {
            ll ny = y + 1;
            ll nx = min(x, lines[ny]);
            ll code = encode(nx, ny);
            if (!visited.count(code)) {
                if (nx == ex-1 && ny == ey-1) {
                    cout << dist + 1;
                    return 0;
                }
                visited.insert(code);
                fronta.push({nx, ny, dist + 1});
            }
        }
    }

    return 0;
}

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