Cod sursa(job #1518747)

Utilizator hrazvanHarsan Razvan hrazvan Data 6 noiembrie 2015 12:21:38
Problema Curcubeu Scor 50
Compilator c Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <stdio.h>
#define MAXN 1000000
int st[MAXN], dr[MAXN], col[MAXN], last[MAXN];
int lcol[MAXN];
int stiv[MAXN], rez[MAXN];

int stata(int x, int n){
  int d = 0;
  stiv[0] = x;
  rez[0] = -1;
  while(d >= 0){
    if(rez[d] == -1){
      if(stiv[d] >= n || (stiv[d] < n && lcol[stiv[d]] == 0)){
        if(d != 0)
          rez[d - 1] = stiv[d];
        rez[d] = stiv[d];
        d--;
      }
      else{
        stiv[d + 1] = last[stiv[d]];
        rez[d + 1] = -1;
        d++;
      }
    }
    else{
      last[stiv[d]] = rez[d];
      if(d != 0)
        rez[d - 1] = rez[d];
      d--;
    }
  }
  return rez[0];
}

int main(){
  FILE *in = fopen("curcubeu.in", "r");
  int i, ca, cb, cc, aux, n;
  fscanf(in, "%d%d%d%d", &n, &ca, &cb, &cc);
  fclose(in);
  for(i = 1; i < n; i++){
    st[i] = ca;  dr[i] = cb;  col[i] = cc;
    if(st[i] > dr[i]){
      aux = st[i];  st[i] = dr[i];  dr[i] = aux;
    }
    ca = 1LL * ca * (i + 1) % n;
    cb = 1LL * cb * (i + 1) % n;
    cc = 1LL * cc * (i + 1) % n;
    last[i] = i + 1;
  }
  int poz;
  for(i = n - 1; i > 0; i--){
    poz = stata(st[i], n);
    while(poz <= dr[i]){
      lcol[poz] = col[i];
      poz = stata(poz, n);
    }
    stata(st[i], n);
  }
  FILE *out = fopen("curcubeu.out", "w");
  for(i = 1; i < n; i++)
    fprintf(out, "%d\n", lcol[i]);
  fclose(out);
  return 0;
}