Submission #1137581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137581		SyedSohaib_123	Text editor (CEOI24_editor)	C++20	19 / 100	100 ms	43528 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define append push_back
#define int long long

const int N=1e3,LG=1e4;
int mod=1e9+7;

int mn[N][LG];

void solve(int tst) {
    int n;
    cin>>n;
    int a,b,x,y;
    cin>>a>>b>>x>>y;
    vector<int>v(n+1,0);
    int mx=0;
    for(int i=1;i<=n;i++){
        cin>>v[i];
        mx=max(mx,v[i]);
        v[i]++;
    }
    if(n<=2){
        if(x==1){
            cout<<min({abs(b-y),y+1-(a==2),v[1]-y+2-(a==2)});
        }
        else if(x==2){
            cout<<(a==1)<<endl;
        }
        return;
    }
    if(mx<=1e4 and n<=1e3){
        mn[a][b]=1;
        deque<pair<int,int>>d;
        d.append({a,b});
        while(d.size()){
            auto [i,j]=d[0];
            d.pop_front();
            //up
            if(i>1 and !mn[i-1][min(v[i-1],j)]){
                mn[i-1][min(v[i-1],j)]=mn[i][j]+1;
                d.append({i-1,min(v[i-1],j)});
            }
            // down
            if(i<n and !mn[i+1][min(v[i+1],j)]){
                mn[i+1][min(v[i+1],j)]=mn[i][j]+1;
                d.append({i+1,min(v[i+1],j)});
            }
            //->
            if(!(i==n and j==v[n])){
                if(j!=v[i]){
                    if(!mn[i][j+1]){
                        mn[i][j+1]=mn[i][j]+1;
                        d.append({i,j+1});
                    }
                }
                else{
                    if(!mn[i+1][1]){
                        mn[i+1][1]=mn[i][j]+1;
                        d.append({i+1,1});
                    }
                }
            }
            //<-
            if(!(i==1 and j==1)){
                if(j!=1){
                    if(!mn[i][j-1]){
                        mn[i][j-1]=mn[i][j]+1;
                        d.append({i,j-1});
                    }
                }
                else{
                    if(!mn[i-1][v[i-1]]){
                        mn[i-1][v[i-1]]=mn[i][j]+1;
                        d.append({i-1,v[i-1]});
                    }
                }
            }
        }
    }
    cout<<mn[x][y]-1<<endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int i = 0; i < t; i++) {
        solve(i);
    }
}

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