oj.uz

Submission #1081054

# Submission time Handle Problem Language Result Execution time Memory
1081054 2024-08-29T17:38:58 Z oscar1f Text editor (CEOI24_editor) C++17
14 / 100
 4000 ms 838504 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19036 KB Output is correct
2 Execution timed out 4126 ms 838504 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 6 ms 19036 KB Output is correct
4 Correct 598 ms 29272 KB Output is correct
5 Correct 656 ms 30256 KB Output is correct
6 Correct 44 ms 19804 KB Output is correct
7 Correct 596 ms 30196 KB Output is correct
8 Correct 2326 ms 59116 KB Output is correct
9 Correct 1850 ms 52012 KB Output is correct
10 Correct 1879 ms 52836 KB Output is correct
11 Correct 1779 ms 52040 KB Output is correct
12 Correct 1927 ms 59316 KB Output is correct
13 Correct 1940 ms 59748 KB Output is correct
14 Correct 1875 ms 59604 KB Output is correct
15 Correct 1411 ms 59288 KB Output is correct
16 Correct 1271 ms 59244 KB Output is correct
17 Correct 1287 ms 59504 KB Output is correct
18 Correct 1326 ms 59356 KB Output is correct
19 Correct 1182 ms 59752 KB Output is correct
20 Correct 1661 ms 55420 KB Output is correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 6 ms 19036 KB Output is correct
4 Execution timed out 4126 ms 838504 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19036 KB Output is correct
2 Execution timed out 4126 ms 838504 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 6 ms 19036 KB Output is correct
4 Execution timed out 4126 ms 838504 KB Time limit exceeded
5 Halted 0 ms 0 KB -