Cod sursa(job #2750527)

Utilizator linte_robertLinte Robert linte_robert Data 11 mai 2021 19:14:27
Problema Schi Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

int main(){
    vector < int > succesori;
    vector < int > predecesori;
    vector < int > locuri;
    int n;
    ifstream fin("schi.in");
    ofstream fout("schi.out");
    fin >> n;
    succesori.push_back(0);
    predecesori.push_back(0);
    locuri.push_back(0);

    for( int i = 1; i <= n; i++ ){
        int loc;
        fin >> loc;
        if( i == 1 ){
            succesori.push_back(-1);
            predecesori.push_back(-1);
            locuri.push_back(1);
        }
        else{
            if( i == loc ){
                int j = 1;
                while( predecesori[j] != -1 ) j++;
                predecesori.push_back(-1);
                succesori.push_back(j);
                locuri.push_back(loc);
                predecesori[j] = i;
            }
            else{
                if( loc != 1 ){
                    int j = 1;
                    while( locuri[j] != loc ) j++;
                    predecesori[ succesori[j] ] = i;
                    succesori.push_back( succesori[j] );
                    predecesori.push_back(j);
                    locuri.push_back(loc);
                    succesori[j] = i;
                    while( j != -1 ){
                        locuri[j]++;
                        j = predecesori[j];
                    }
                }
                else{
                    int j = 1;
                    while( locuri[j] != 1 ) j++;
                    for( int k = 1; k < locuri.size(); k++ ){
                        locuri[k]++;
                    }
                    succesori[j] = i;
                    predecesori.push_back(j);
                    succesori.push_back(-1);
                    locuri.push_back(loc);
                }
            }
        }
    }

    int i = 1;
    while( locuri[i] != 1 ) i++;
    while( predecesori[i] != -1 ){
        fout << i << endl;
        i = predecesori[i];
    }
    fout << i;
}