Cod sursa(job #2811029)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 30 noiembrie 2021 21:50:53
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");

const int kN = 1e6;
int a[kN], b[kN], c[kN], sol[kN];
bitset<1 + kN> vis;

struct DSU {
  vector<int> p, sz;

  DSU(int n) {
    p.resize(n + 1);
    iota(p.begin(), p.end(), 0);
    sz.assign(n + 1, 1);
  }

  int root(int x) {
    if (x == p[x]) {
      return x;
    }
    return p[x] = root(p[x]);
  }

  bool unite(int u, int v) {
    int x = root(u), y = root(v);
    if (x == y) {
      return false;
    }
    if (sz[x] > sz[y]) {
      swap(x, y);
    }
    p[x] = y;
    sz[y] += sz[x];
    return true;
  }

  int getNext(int x) {
    return x + sz[root(x)];
  }
};

void testCase() {
  int n;
  fin >> n >> a[1] >> b[1] >> c[1];
  for (int i = 2; i < n; ++i) {
    a[i] = (int64_t)a[i - 1] * i % n;
    b[i] = (int64_t)b[i - 1] * i % n;
    c[i] = (int64_t)c[i - 1] * i % n;
  }
  DSU t(n);
  for (int i = n - 1; i > 0; --i) {
    int l = min(a[i], b[i]), r = max(a[i], b[i]);
    if (l == 0) {
      l = 1;
    }
    if (vis[l]) {
      l = t.getNext(l);
    }
    while (l <= r) {
      vis[l] = true;
      sol[l] = c[i];
      if (1 < l && vis[l - 1]) {
        t.unite(l - 1, l);
      }
      if (l + 1 < n - 1 && vis[l + 1]) {
        t.unite(l, l + 1);
      }
      l = t.getNext(l);
    }
  }
  for (int i = 1; i < n; ++i) {
    fout << sol[i] << '\n';
  }
}

int main() {
  int tests = 1;
  for (int tc = 1; tc <= tests; ++tc) {
    testCase();
  }
  fin.close();
  fout.close();
  return 0;
}