Cod sursa(job #2811032)

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

using namespace std;

class OutParser {
private:
    FILE *fout;
    char *buff;
    int sp;

    void write_ch(char ch) {
        if (sp == 50000) {
            fwrite(buff, 1, 50000, fout);
            sp = 0;
            buff[sp++] = ch;
        } else {
            buff[sp++] = ch;
        }
    }


public:
    OutParser(const char* name) {
        fout = fopen(name, "w");
        buff = new char[50000]();
        sp = 0;
    }
    ~OutParser() {
        fwrite(buff, 1, sp, fout);
        fclose(fout);
    }

    OutParser& operator << (int vu32) {
        if (vu32 <= 9) {
            write_ch(vu32 + '0');
        } else {
            (*this) << (vu32 / 10);
            write_ch(vu32 % 10 + '0');
        }
        return *this;
    }

    OutParser& operator << (long long vu64) {
        if (vu64 <= 9) {
            write_ch(vu64 + '0');
        } else {
            (*this) << (vu64 / 10);
            write_ch(vu64 % 10 + '0');
        }
        return *this;
    }

    OutParser& operator << (char ch) {
        write_ch(ch);
        return *this;
    }
    OutParser& operator << (const char *ch) {
        while (*ch) {
            write_ch(*ch);
            ++ch;
        }
        return *this;
    }
};

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

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

void minSelf(int &x, const int &y) {
  if (y < x) {
    x = y;
  }
}

struct DSU {
  vector<int> p, start, sz;

  DSU(int n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
    start = p;
    sz.assign(n, 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];
    minSelf(start[y], start[x]);
    return true;
  }

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

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();
  return 0;
}