Cod sursa(job #2750411)

Utilizator linte_robertLinte Robert linte_robert Data 11 mai 2021 03:46:25
Problema Schi Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

int main(){
    vector < int > locuri;
    vector < int > succesor;
    vector < int > predecesor;
    locuri.push_back(0);
    succesor.push_back(0);
    predecesor.push_back(0);
    ifstream fin("schi.in");
    ofstream fout("schi.out");
    int n;
    fin >> n;
    for( int i = 1; i <= n; i++ ){
        int loc;
        fin >> loc;
        if( i == 1 ){
            locuri.push_back(loc);
            succesor.push_back(-1);
            predecesor.push_back(-1);
        }
        else{
            if( loc == i ){
                int j = 1;
                while( predecesor[j] != -1 ) j++;
                predecesor[j] = i;
                locuri.push_back(loc);
                succesor.push_back(j);
                predecesor.push_back(-1);
            }
            else{
                int j = 1;
                while( locuri[j] != loc ) j++;
                succesor.push_back( succesor[j] );
                predecesor.push_back(j);
                predecesor[ succesor[j] ] = i;
                succesor[j] = i;
                while( j != -1 ){
                    locuri[j]++;
                    j = predecesor[j];
                }
                locuri.push_back(loc);
            }
        }
    }
    int i = 1;
    while( locuri[i] != 1 ) i++;
    while( predecesor[i] != -1 ){
        fout << i << endl;
        i = predecesor[i];
    }
    fout << i;
}