Submission #1068817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068817		vjudge1	Text editor (CEOI24_editor)	C++17	0 / 100	63 ms	80724 KiB

Main

#include <bits/stdc++.h>
#define div /
#define ll long long

#define fore(i, l, r) for(int i=int(l); i<int(r); i++)
#define sz(a) int((a).size())

using namespace std;

const int INF = 1e9;
const int MX = 5e5 + 23;
const int MOD = 1000000007;
const int MAX_N = 5e5+23;
const int N = 1e6;

int grid[1005][5005],dist[2005][5050],visited[1005][5005],oznacen[1005][5005];

void solve() {
    int n; cin >> n;
    int sl,sc,el,ec;
    cin >> sl >> sc >> el >> ec;
    vector<int>l(5005,0);
    fore(i,0,1003) {
        fore(j,0,5003) {
            dist[i][j] = INF;
            grid[i][j] = 1e6;
        }
    }
    fore(i,1,n+1) {
        cin >> l[i];
        fore(j,1,l[i]+1)
            grid[i][j] = 1;
    }
    queue<pair<int,int>> q;
    dist[sl][sc] = 0;
    visited[sl][sc] = 1;
    q.push({sl,sc});
    while(!q.empty()) {
        pair<int,int> s=q.front(); q.pop();
        int SL = s.first, SC = s.second;
        if((SL+1) < n) {
            if(grid[SL+1][SC] < 1e6) {
                dist[SL+1][SC] = min(dist[SL+1][SC], dist[SL][SC] + grid[SL+1][SC]);
                if(!visited[SL+1][SC])
                    q.push({SL+1,SC});
                visited[SL+1][SC] = 1;
            } else {
                dist[SL+1][l[SL+1]] = min(dist[SL+1][l[SL+1]], dist[SL][SC] + 1);
                if(!oznacen[SL+1][l[SL+1]])
                    q.push({SL+1,l[SL+1]});
                oznacen[SL+1][l[SL+1]] = 1;
            }
        }
        if(SL-1 > 0) {
            if(grid[SL-1][SC] < 1e6) {
                dist[SL-1][SC] = min(dist[SL-1][SC], dist[SL][SC] + grid[SL-1][SC]);
                if(!visited[SL-1][SC])
                    q.push({SL-1,SC});
                visited[SL-1][SC] = 1;
            } else {
                dist[SL-1][l[SL-1]] = min(dist[SL-1][l[SL-1]], dist[SL][SC] + 1);
                if(!oznacen[SL-1][l[SL-1]])
                    q.push({SL-1,l[SL-1]});
                oznacen[SL-1][l[SL-1]] = 1;
            }
        }
        if(SC+1 <= 5000) {
            if(grid[SL][SC+1] < 1e6) {
                dist[SL][SC+1] = min(dist[SL][SC+1], dist[SL][SC] + grid[SL][SC+1]);
                if(!visited[SL][SC+1])
                    q.push({SL,SC+1});
                visited[SL][SC+1] = 1;
            }
        }
        if(SC-1 > 0) {
            if(grid[SL][SC-1] < 1e6) {
                dist[SL][SC-1] = min(dist[SL][SC-1], dist[SL][SC] + grid[SL][SC-1]);
                if(!visited[SL][SC-1])
                    q.push({SL,SC-1});
                visited[SL][SC-1] = 1;
            }
        }
        if(SC == 1 and SL > 1 and SL <= n) { // SPECIAL LEFT PRESS
            dist[SL-1][l[SL-1]] = min(dist[SL-1][l[SL-1]], dist[SL][SC] + 1);
            if(!oznacen[SL-1][l[SL-1]])
                q.push({SL-1,l[SL-1]});
            oznacen[SL-1][l[SL-1]] = 1;
        }
        if(SC == l[SL-1] and SL < n) { // SPECIAL RIGHT PRESS
            dist[SL+1][1] = min(dist[SL+1][1], dist[SL][SC] + 1);
            if(!oznacen[SL+1][1])
                q.push({SL+1, 1});
            oznacen[SL+1][1] = 1;
        }
    }
    cout << dist[el][ec] << endl;
}

int main() {
    ios::sync_with_stdio(false);

    int t=1;
    while(t--) solve();
}

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