Cod sursa(job #2691145)

Utilizator cristi_macoveiMacovei Cristian cristi_macovei Data 27 decembrie 2020 13:39:38
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <algorithm>

const int NMAX = 1e6;

int n;

int color[1 + NMAX];

int next[1 + NMAX];

int a[1 + NMAX], b[1 + NMAX], c[1 + NMAX];

int stack[1 + NMAX];
int stSize;

int getNext(int i) {
  while (next[i] != i) {
    stack[++stSize] = i;
    i = next[i];
  }

  while (stSize > 0) {
    next[stack[stSize]] = i;
    --stSize;
  }

  return i;
}

int main() {
  std::ifstream in("curcubeu.in");
  std::ofstream out("curcubeu.out");

  in >> n >> a[1] >> b[1] >> c[1];

  for (int i = 2; i < n; ++i) {
    a[i] = (int)(((int64_t)a[i - 1] * i) % n);
    b[i] = (int)(((int64_t)b[i - 1] * i) % n);
    c[i] = (int)(((int64_t)c[i - 1] * i) % n);

    if (a[i] > b[i])
      std::swap(a[i], b[i]);
  }

  for (int i = 1; i <= n; ++i)
    next[i] = i;

  for (int q = n - 1; q >= 1; --q) {
    for (int i = getNext(a[q]); i <= b[q]; i = getNext(i + 1)) {
      if (color[i] == 0) {
        color[i] = c[q];
        next[i] = getNext(b[q] + 1);
      }
    }
  }

  for (int i = 1; i < n; ++i)
    out << color[i] << '\n';

  return 0;
}