Submission #1134363

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134363		Aiperiii	Text editor (CEOI24_editor)	C++20	14 / 100	116 ms	43740 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
using namespace std;

vector <int> dis[1005];
signed main(){
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    int n;
    cin>>n;
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    
    
    
    
    
    
    vector <int> l(n);
    
    for(int i=0;i<n;i++){
        cin>>l[i];
        if(n>=3){
            dis[i+1].pb(-1);
            for(int j=0;j<l[i]+1;j++){
                dis[i+1].pb(-1);
            }
        }
        
       
    }
    if(n==1){
        cout<<abs(b-d)<<"\n";
        return 0;
    }
    
    if(n==2){
        if(a==c){
            cout<<abs(b-d)<<"\n";
        }
        else{
            if(b<d){
                swap(a,c);
                swap(b,d);
            }
            if(b==d)cout<<1<<"\n";
            
            else {
                int ans=b-d+1;
                if(a==1){
                    if(b<=l[1]+1){
                        ans=min(ans,l[1]+1-b+1+l[1]+1-d);
                    }
                    ans=min(ans,l[0]+1-b+1+l[1]+1-d);
                }
                else{
                    if(b<=l[0]+1){
                        ans=min(ans,l[0]+1-b+1+l[0]+1-d);
                    }
                    ans=min(ans,l[1]+1-b+1+l[0]+1-d);
                }
                cout<<ans<<"\n";
            }
            
            
        }
        
        return 0;
    }
    
    dis[a][b]=0;
    // aaaa 
    //   bbbbb
    queue <pair <int,int> >  q;
    q.push({a,b});
    
    while(!q.empty()){
        int x=q.front().ff;
        int y=q.front().ss;
        q.pop();
        if(y-1>=1){
            if(dis[x][y-1]==-1){
                dis[x][y-1]=dis[x][y]+1;
                q.push({x,y-1});
            }
        }
        else if(x-1>=1){
            if(dis[x-1][l[x-2]+1]==-1){
                dis[x-1][l[x-2]+1]=dis[x][y]+1;
                q.push({x-1,l[x-2]+1});
            }
        }
        
        if(y+1<=l[x-1]+1){
            if(dis[x][y+1]==-1){
                dis[x][y+1]=dis[x][y]+1;
                q.push({x,y+1});
            }
        }
        else if(x+1<=n){
            if(dis[x+1][1]==-1){
                dis[x+1][1]=dis[x][y]+1;
                q.push({x+1,1});
            }
        }
        
        
        if(x-1>=1){
            if(dis[x-1][min(y,l[x-2]+1)]==-1){
                dis[x-1][min(y,l[x-2]+1)]=dis[x][y]+1;
                q.push({x-1,min(y,l[x-2]+1)});
            }
        }
        
        if(x+1<=n){
            if(dis[x+1][min(y,l[x]+1)]==-1){
                dis[x+1][min(y,l[x]+1)]=dis[x][y]+1;
                q.push({x+1,min(y,l[x]+1)});
            }
        }
    }
    cout<<dis[c][d]<<"\n";
}
/*

*/

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