제출 #1081054

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1081054		oscar1f	Text editor (CEOI24_editor)	C++17	14 / 100	4126 ms	838504 KiB

Main

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

#define int long long

const int TAILLE_MAX=1000*1000+5,DECA=(1<<20),INFINI=(int)1000*1000*1000*1000*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;
int arbreMin[2*DECA];

int calcMin(int deb,int fin) {
    if (deb==fin) {
        return arbreMin[deb];
    }
    if (deb%2==1) {
        return min(arbreMin[deb],calcMin(deb+1,fin));
    }
    if (fin%2==0) {
        return min(arbreMin[fin],calcMin(deb,fin-1));
    }
    return calcMin(deb/2,fin/2);
}

int calcDistNorm(int lig1,int col1,int lig2,int col2) {
    if (lig1>=lig2) {
        swap(lig1,lig2);
        swap(col1,col2);
    }
    int mini=calcMin(DECA+lig1,DECA+lig2);
    return lig2-lig1+abs(col1-col2)+2*max((int)0,min(col1,col2)-mini);
}

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=0;i<2*DECA;i++) {
        arbreMin[i]=INFINI;
    }
    for (int i=1;i<=nbLig;i++) {
        cin>>tailleLig[i];
        interres.insert(tailleLig[i]+1);
        for (int j=1;j<=tailleLig[i];j++) {
            interres.insert(j);
        }
        arbreMin[DECA+i]=tailleLig[i]+1;
    }
    for (int i=DECA-1;i>0;i--) {
        arbreMin[i]=min(arbreMin[2*i],arbreMin[2*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]));
                }
            }
        }
    }
    int rep=calcDistNorm(ligDeb,colDeb,ligFin,colFin);
    for (int i=1;i<=nbLig;i++) {
        rep=min(rep,dist[i][0]+calcDistNorm(i,1,ligFin,colFin));
        rep=min(rep,dist[i][corres[tailleLig[i]+1]]+calcDistNorm(i,tailleLig[i]+1,ligFin,colFin));
    }
    cout<<rep<<endl;
    /*for (int i=1;i<=nbLig;i++) {
        for (int j=0;j<nbCol;j++) {
            cout<<dist[i][j]<<"\t";
        }
        cout<<endl;
    }
    cout<<dist[ligFin][corres[colFin]]<<endl;*/
    return 0;
}
 

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