Submission #1081001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081001		oscar1f	Text editor (CEOI24_editor)	C++17	56 / 100	1951 ms	1048576 KiB

Main

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

#define int long long

const int TAILLE_MAX=1000*1000+5;
int nbLig,ligDeb,colDeb,ligFin,colFin,nbCol;
set<int> interres;
vector<int> listeCol;
unordered_map<int,int> corres;
int tailleLig[TAILLE_MAX],posCol[TAILLE_MAX];
vector<vector<int>> dist;
priority_queue<tuple<int,int,int>> possi;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>nbLig>>ligDeb>>colDeb>>ligFin>>colFin;
    interres.insert(colDeb);
    interres.insert(colFin);
    interres.insert(1);
    for (int i=1;i<=nbLig;i++) {
        cin>>tailleLig[i];
        interres.insert(tailleLig[i]+1);
    }
    for (int i:interres) {
        corres[i]=listeCol.size();
        posCol[listeCol.size()]=i;
        listeCol.push_back(i);
    }
    nbCol=listeCol.size();
    vector<int> construc;
    for (int j=0;j<nbCol;j++) {
        construc.push_back(-1);
    }
    for (int i=1;i<=nbLig+1;i++) {
        dist.push_back(construc);
    }
    int lig,col,distCour;
    possi.push(make_tuple(0,ligDeb,corres[colDeb]));
    while (!possi.empty()) {
        distCour=-get<0>(possi.top());
        lig=get<1>(possi.top());
        col=get<2>(possi.top());
        possi.pop();
        if (dist[lig][col]==-1) {
            dist[lig][col]=distCour;
            //gauche
            if (col!=0) {
                possi.push(make_tuple(-(distCour+posCol[col]-posCol[col-1]),lig,col-1));
            }
            else if (lig>1) {
                possi.push(make_tuple(-(distCour+1),lig-1,corres[tailleLig[lig-1]+1]));
            }
            
            //droite
            if (posCol[col]!=tailleLig[lig]+1) {
                possi.push(make_tuple(-(distCour+posCol[col+1]-posCol[col]),lig,col+1));
            }
            else if (lig<nbLig) {
                possi.push(make_tuple(-(distCour+1),lig+1,0));
            }
            
            //haut
            if (lig>1) {
                if (tailleLig[lig-1]+1>=posCol[col]) {
                    possi.push(make_tuple(-(distCour+1),lig-1,col));
                }
                else {
                    possi.push(make_tuple(-(distCour+1),lig-1,corres[tailleLig[lig-1]+1]));
                }
            }

            //bas
            if (lig<nbLig) {
                if (tailleLig[lig+1]+1>=posCol[col]) {
                    possi.push(make_tuple(-(distCour+1),lig+1,col));
                }
                else {
                    possi.push(make_tuple(-(distCour+1),lig+1,corres[tailleLig[lig+1]+1]));
                }
            }
        }
    }
    /*for (int i=1;i<=nbLig;i++) {
        for (int j=0;j<nbCol;j++) {
            cout<<dist[i][j]<<"   ";
        }
        cout<<endl;
    }*/
    cout<<dist[ligFin][corres[colFin]]<<endl;
    return 0;
}
 

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