Cod sursa(job #1788155)

Utilizator tudorcomanTudor Coman tudorcoman Data 25 octombrie 2016 18:48:33
Problema Curcubeu Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb

#include <cstdio>

const int maxN = 1000005;
int A[maxN + 5], B[maxN + 5], C[maxN + 5];
int ans[maxN + 5], v[maxN + 5];

void quickswap(int &x, int &y) {
  if(x != y) {
    x = x xor y;
    y = x xor y;
    x = x xor y;
  }
}

void compute(int *a, int i, int n) {
  a[i] = static_cast<long long>(a[i - 1] * i) % n;
}

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

  int N;
  scanf("%d %d %d %d", &N, &A[1], &B[1], &C[1]);

  if(A[1] > B[1])
    quickswap(A[1], B[1]);

  for(int i = 2; i < N; ++ i) {
    compute(A, i, N);
    compute(B, i, N);
    compute(C, i, N);

    if(A[i] > B[i])
      quickswap(A[i], B[i]);
  }

  for(int i = N - 1; i; -- i) {
    int j = A[i];
    while(j <= B[i]) {
      if(!ans[j]) {
        ans[j] = C[i];
        v[j ++] = B[i] + 1;
      } else
        j = v[j];
    }
  }

  for(int i = 1; i < N; ++ i)
    printf("%d\n", ans[i]);
  return 0;
}