Cod sursa(job #2627046)

Utilizator euyoTukanul euyo Data 9 iunie 2020 14:45:31
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <fstream>
#define MAXQ 1000000

using namespace std;

struct update {
  int st, dr, col;
} q[MAXQ];

int urm[MAXQ];
int sol[MAXQ];

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

int findRoot( int x ) {
  if ( urm[x] == x ) {
    return x;
  }
  return urm[x] = findRoot( urm[x] );
}
void join( int x, int y ) {
  urm[x] = urm[findRoot( x )] = findRoot( y );
}

int main() {
  int n, i, a, b, c, ind;
  
  fin >> n >> a >> b >> c;
  for ( i = n - 1; i >= 1; --i ) {
	q[i].st = (a < b ? a : b);
	q[i].dr = (a + b) - q[i].st;
	q[i].col = c;
	urm[i] = i;
	a = (a * i) % n;
	b = (b * i) % n;
	c = (c * i) % n;
  }
  for ( i = 1; i <= n - 1; ++i ) {
	/*printf( "%d %d %d\n", q[i].st, q[i].dr, q[i].col );
	for ( ind = 1; ind <= n - 1; ++ind ) {
	  printf( "%d %d\n", sol[ind], findRoot( ind ) );
	}
	printf( "\n" );*/
	ind = q[i].st;
	while ( ind < q[i].dr ) {
	  if ( sol[ind] == 0 && sol[ind + 1] == 0 ) {
        join( ind, ind + 1 );
	    sol[ind] = q[i].col;
		++ind;
	  } else if ( sol[ind] ) {
        ind = findRoot( ind ) + 1;
	  } else {
		sol[ind] = q[i].col;
		ind = findRoot( ind + 1 ) + 1;
	  }
	}
	if ( sol[q[i].dr] == 0 ) {
	  sol[q[i].dr] = q[i].col;
	}
  }
  for ( i = 1; i <= n - 1; ++i ) {
	fout << sol[i] << "\n";
  }
  fin.close();
  fout.close();
  return 0;
}