Submission #1137689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137689		Muhammad_Aneeq	Text editor (CEOI24_editor)	C++20	45 / 100	4099 ms	112360 KiB

Main

/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/

#include <iostream>
#include <map>
#include <queue>
#warning check the output
using namespace std;
int const N=1e6+10;
int n;
int a[N]={};
map<pair<int,int>,int>vals;
void bfs(int i,int j)
{
    queue<pair<int,int>>Q;
    Q.push({i,j});
    while (Q.size())
    {
        int x,y;
        tie(x,y)=Q.front();
        Q.pop();
        int x1=x-1,y1=y;
        if (x1>0)
        {
            y1=min(y,a[x1]+1);
            if (vals.find({x1,y1})==vals.end())
                vals[{x1,y1}]=2e9+10;
            if (vals[{x1,y1}]>vals[{x,y}]+1)
            {
                Q.push({x1,y1});
                vals[{x1,y1}]=vals[{x,y}]+1;
            }
        }
        x1=x+1,y1=y;
        if (x1<=n)
        {
            y1=min(y1,a[x1]+1);
            if (vals.find({x1,y1})==vals.end())
                vals[{x1,y1}]=2e9+10;
            if (vals[{x1,y1}]>vals[{x,y}]+1)
            {
                Q.push({x1,y1});
                vals[{x1,y1}]=vals[{x,y}]+1;
            }
        }
        x1=x+1,y1=1;
        if (x1<=n)
        {
            if (vals.find({x1,y1})==vals.end())
                vals[{x1,y1}]=2e9+10;
            if (vals[{x1,y1}]>vals[{x,y}]+a[x]+2-y)
            {
                Q.push({x1,y1});
                vals[{x1,y1}]=vals[{x,y}]+a[x]-y+2;
            }
        }
        x1=x-1;
        if(x1>0)
        {
            y1=a[x1]+1;
            if (vals.find({x1,y1})==vals.end())
                vals[{x1,y1}]=2e9+10;
            if (vals[{x1,y1}]>vals[{x,y}]+y)
            {
                Q.push({x1,y1});
                vals[{x1,y1}]=vals[{x,y}]+y;
            }
        }
    }
}
inline void solve()
{
    cin>>n;
    int sl,sc;
    cin>>sl>>sc;
    int el,ec;
    cin>>el>>ec;
    vals[{sl,sc}]=0;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    bfs(sl,sc);
    int ans=2e9+10;
    for (auto i:vals)
    {
        int x,y;
        tie(x,y)=i.first;
        if (el!=x)
            continue;
        ans=min(ans,abs(el-x)+abs(ec-y)+i.second);
    }
    cout<<ans<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    for (int i=1;i<=t;i++)
    {
        solve();
    }
}

Compilation message (stderr)

Main.cpp:10:2: warning: #warning check the output [-Wcpp]
   10 | #warning check the output
      |  ^~~~~~~

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