Submission #1081045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081045		abouton	Text editor (CEOI24_editor)	C++17	5 / 100	13 ms	24152 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct piv
{
    int l, c;
    bool operator<(const piv &autre) const
    {
        if (l == autre.l) return c < autre.c;
        return l < autre.l;
    }
};

int N;
int lignes[(int)1e6+1];
int lD, cD;
int lF,cF;
vector<pair<int,int>> acc[(int)1e6+1];
map<piv, int> dist;
vector<pair<int,int>> surL;

vector<piv> vois(piv actu)
{
    vector<piv> ans;
    int lig = actu.l, col = actu.c;
    if (lig != 0)
    {
        ans.push_back({lig-1, min(lignes[lig-1]-1, col)});
    }
    if (lig != N-1)
    {
        ans.push_back({lig+1, min(lignes[lig+1]-1, col)});
    }
    if (col == 0 && lig != 0)
    {
        ans.push_back({lig-1, lignes[lig-1]-1});
    }
    if (col = lignes[lig]-1)
    {
        ans.push_back({lig+1, 0});
    }
    //for (auto i : ans) cout << i.l << ' ' << i.c << ' '; cout << '\n';
    return ans;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin >> N;
    cin >> lD >> cD >> lF >> cF;
    lD--; cD--; lF--; cF--;
    for (int i = 0; i < N; i ++)
    {
        cin >> lignes[i];
        lignes[i]++;
    }

    queue<piv> bfs;
    bfs.push({lD,cD});
    dist[{lD,cD}] = 0;
    while (!bfs.empty())
    {
        auto best = bfs.front();
        bfs.pop();
        //if (dist.count(best)) continue;
        for (piv nouv : vois(best))
        {
            if (!dist.count(nouv))
            {
                bfs.push({nouv.l, nouv.c});
                dist[nouv] = dist[best]+1;
            }
        }
    }

    /*for (auto it = dist.begin(); it != dist.end(); it ++)
    {
        cout << (*it).first.l << ' ' << (*it).first.c << " : " << (*it).second << '\n';
    }*/

    for (auto it = dist.begin(); it != dist.end(); it ++)
    {
        auto mec = *it;
        if (mec.first.l == lF)
        {
            surL.push_back({mec.first.c, mec.second});
        }
    }

    int mini = 1000000000000000000;
    for (auto mec : surL)
    {
        mini = min(mini, mec.second + abs(mec.first-cF));
    }
    cout << mini<<'\n';
}

Compilation message (stderr)

Main.cpp: In function 'std::vector<piv> vois(piv)':
Main.cpp:39:13: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   39 |     if (col = lignes[lig]-1)
      |         ~~~~^~~~~~~~~~~~~~~

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