Cod sursa(job #2627074)

Utilizator euyoTukanul euyo Data 9 iunie 2020 17:32:14
Problema Curcubeu Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <stdio.h>
#define MAXQ 1000000

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

int urm[MAXQ + 1];
int sol[MAXQ + 1];

static inline int findRoot( int x ) {
  int r, xc = x, k;

  while ( x != urm[x] ) {
	x = urm[x];
  }
  r = x;
  while ( xc != urm[xc] ) {
	k = urm[xc];
	urm[xc] = r;
	xc = k;
  }
  return r;
}
static inline void join( int x, int y ) {
  urm[x] = y;
}

int main() {
  FILE *fin = fopen( "curcubeu.in", "r" );
  FILE *fout = fopen( "curcubeu.out", "w" );
  int n, i, a, b, c, ind, rind;
  
  fscanf( fin, "%d%d%d%d", &n, &a, &b, &c );
  for ( i = 1; i <= n; ++i ) {
	q[i].st = (a < b ? a : b);
	q[i].dr = (a + b) - q[i].st;
	q[i].col = c;
	urm[i] = i;
	a = ((long long)a * (i + 1)) % n;
	b = ((long long)b * (i + 1)) % n;
	c = ((long long)c * (i + 1)) % n;
  }
  for ( i = n - 1; i >= 1; --i ) {
	ind = q[i].st;
	while ( ind <= q[i].dr ) {
	  rind = findRoot( ind );
	  join( ind, q[i].dr );
	  if ( sol[ind] == 0 ) {
		sol[ind] = q[i].col;
	  }
	  ind = rind + 1;
	}
  }	
  for ( i = 1; i <= n - 1; ++i ) {
	fprintf( fout, "%d\n", sol[i] );
  }
  fclose( fin );
  fclose( fout );
  return 0;
}