Cod sursa(job #1621178)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 29 februarie 2016 17:18:47
Problema Curcubeu Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include<fstream>

using namespace std;

ifstream fin( "curcubeu.in" ); ofstream fout( "curcubeu.out" );

const int nmax = 1e6;
int lista[ nmax + 1 ];
int ans[ nmax + 1 ];
int a[ nmax + 1 ], b[ nmax + 1 ], c[ nmax + 1 ];

void colorare( int pos, int ind ) {
    if ( pos > b[ ind ] ) {
        return ;
    }
    if ( ans[ pos ] == 0 )
        ans[ pos ] = c[ ind ];
    colorare( lista[ pos ], ind );
    lista[ pos ] = lista[ b[ ind ] ];
}
int main() {
    int n;
    fin >> n >> a[ 1 ] >> b[ 1 ] >> c[ 1 ];
    for( int i = 2; i <= n - 1; ++ i ) {
        a[ i ] = ( 1LL * a[ i - 1 ] * i ) % n;
        b[ i ] = ( 1LL * b[ i - 1 ] * i ) % n;
        if ( a[ i ] > b[ i ] ) {
            int aux = a[ i ];
            a[ i ] = b[ i ];
            b[ i ] = aux;
        }
        c[ i ] = ( 1LL * c[ i - 1 ] * i ) % n;
    }
    for( int i = 0; i < n; ++ i ) {
        lista[ i ] = i + 1;
    }

    for( int i = n - 1; i > 0; -- i ) {
        if ( a[ i ] > b[ i ] ) {
            swap( a[ i ], b[ i ] );
        }
        colorare( a[ i ], i );
        lista[ a[ i ] ] = lista[ b[ i ] ];
    }
    for( int i = 1; i < n; ++ i ) {
        fout << ans[ i ] << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}