Submission #1214303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214303		spetr	Text editor (CEOI24_editor)	C++20	0 / 100	4107 ms	317760 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll mmod = 998244353;  
#define vl vector<long long>
#define vll vector<vector<long long>>

ll pow(ll x, ll n, ll mod){
    if (n == 0){
        return 1;
    }
ll half = pow(x, n / 2, mod);
ll half_square = (half * half) % mod;

if (n % 2 == 0) {
    return half_square;
} else {
    return (half_square * x) % mod;
}
}   


ll inversion_x(ll x, ll m){
    ll vysledek = pow(x,m-2);
    return vysledek;
}


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

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

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

    vl lines;
    for (ll i = 0; i<n; i++){
        ll num;
        cin >> num;
        lines.push_back(num);
    }



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

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

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

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

        auto je = visited.find({x,y});
        if (1 == 1){
            
            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; // invalid
            }
            if (nx >= 0) {
                if (visited.find({nx,ny}) == visited.end()) {
                    if (nx == ex-1 && ny == ey-1) {
                        cout << dist + 1;
                        return 0;
                    }
                    visited.insert({nx,ny});
                    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; // invalid
            }
            if (nx >= 0) {
                if (visited.find({nx,ny}) == visited.end()) {
                    if (nx == ex-1 && ny == ey-1) {
                        cout << dist + 1;
                        return 0;
                    }
                    visited.insert({nx,ny});
                    fronta.push({nx, ny, dist + 1});
                }
            }
        }

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

        // Move down
        if (y < n - 1) {
            ll ny = y + 1;
            ll nx = x > lines[ny] ? lines[ny] : x;
                if (visited.find({nx,ny}) == visited.end()) {
                    if (nx == ex-1 && ny == ey-1) {
                    cout << dist + 1;
                    return 0;
                }
                    visited.insert({nx,ny});
                    fronta.push({nx, ny, dist + 1});
            }
        
           
        }
    }
    return 0;
}

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