Cod sursa(job #2052241)

Utilizator cella.florescuCella Florescu cella.florescu Data 30 octombrie 2017 12:06:12
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6;

struct col {
  int a, b, c;
} v[MAXN];

int ans[MAXN + 1], nxt[MAXN + 1];

inline int find_nxt(int pos) {
  int f;
  for (f = pos; nxt[f] != f; f = nxt[f]) {}
  while (pos != f) {
    int aux = nxt[pos];
    nxt[pos] = f;
    pos = aux;
  }
  return f;
}

int main()
{
    int n;
    ifstream fin("curcubeu.in");
    fin >> n >> v[1].a >> v[1].b >> v[1].c;
    fin.close();
    for (int i = 2; i < n; ++i)
      v[i] = {(1LL * v[i - 1].a * i) % n, (1LL * v[i - 1].b * i) % n, (1LL * v[i - 1].c * i) % n};
    for (int i = 1; i <= n; ++i)
      nxt[i] = i;
    for (int i = n - 1; i > 0; --i) {
      if (v[i].a > v[i].b)
        swap(v[i].a, v[i].b);
      int pos = find_nxt(v[i].a);
      while (pos <= v[i].b) {
        ans[pos] = v[i].c;
        nxt[pos] = pos + 1;
        pos = find_nxt(pos);
      }
    }
    ofstream fout("curcubeu.out");
    for (int i = 1; i < n; ++i)
      fout << ans[i] << '\n';
    fout.close();
    return 0;
}