Cod sursa(job #860972)

Utilizator veleanduAlex Velea veleandu Data 20 ianuarie 2013 21:00:57
Problema Curcubeu Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <cstdio>

#include <algorithm>
#include <vector>

using namespace std;

	#define max_n 1000005

int n,a,b,c;
int i,j;

int Color[ max_n ], Next[ max_n ];

struct triplet {
	int a,b,c;
	triplet ( int x, int y, int z ){
		a=x;
		b=y;
		c=z;
	}
} ;
vector <triplet> Plank;

int main(){

	freopen ("curcubeu.in","r",stdin);
	freopen ("curcubeu.out","w",stdout);

    scanf ("%d%d%d%d", &n, &a, &b, &c );
	n--;
	Plank.push_back( triplet ( a,b,c ) );
	for ( i=2; i<=n; ++i ){
		Plank.push_back( 
			triplet( 
				( 1LL*Plank.back().a * i )%( n+1 ), 
				( 1LL*Plank.back().b * i )%( n+1 ), 
				( 1LL*Plank.back().c * i )%( n+1 ) 
			) );
	}
 /*   for ( i=0; i<Plank.size(); ++i ){
		printf("%d %d %d\n", Plank[ i ].a, Plank[ i ].b, Plank[ i ].c );
	}*/
	for ( i=Plank.size()-1; i>=0; --i ){
		if ( Plank[ i ].a > Plank[ i ].b ){
			swap ( Plank[ i ].a , Plank[ i ].b );
		}
		for ( j = Plank[ i ].a; j<= Plank[ i ].b; ){
            if ( !Color[ j ] ){
				Color[ j ] = Plank[ i ].c;
				Next[ j ] = Plank[ i ].b+1;
				++j;
			}
			else{
/*				int aux = Next[ j ];
				if ( Next[ j ] < Plank[ i ].b+1 ){
					Next[ j ] = Plank[ i ].b+1;
				}
				j = aux;*/
				j = Next[ j ];
			}
		}
	}
	for ( i=1; i<=n; ++i ){
		printf("%d\n", Color[ i ]);
	}
	return 0;
}