Cod sursa(job #2774604)

Utilizator racsosabeVictor Racso Galvan Oyola racsosabe Data 12 septembrie 2021 02:51:59
Problema Curcubeu Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <bits/stdc++.h>
using namespace std;

void setIO(string name, bool input = true, bool output = true){
  string inputname = name + ".in";
  string outputname = name + ".out";
  if(input) freopen(inputname.c_str(), "r", stdin);
  if(output) freopen(outputname.c_str(), "w", stdout);
}

void solve(int n, vector<int> &A, vector<int> &B, vector<int> &C){
  n--;
  for(int i = 0; i < n; i++){
    if(A[i] > B[i]) swap(A[i], B[i]);
    A[i]--; B[i]--;
  }
  vector<int> res(n, 0);
  vector<int> par(n);
  vector<int> nxt(n);
  iota(par.begin(), par.end(), 0);
  iota(nxt.begin(), nxt.end(), 0);

  function<int(int)> get = [&] (int x) -> int {
    return par[x] == x ? x : par[x];
  };

  function<void(int, int)> join = [&] (int a, int b) -> void {
    a = get(a);
    b = get(b);
    if(a == b) return;
    par[a] = b;
  };

  for(int i = n - 1; i >= 0; i--){
    int l = A[i], r = B[i];
    while(l <= r and get(l) <= r){
      l = get(l);
      if(l + 1 < n) join(l, l + 1);
      if(!res[l]) res[l] = C[i];
      l++;
    }
  }
  for(int i = 0; i < n; i++){
    printf("%d\n", res[i]);
  }
}

int main(){
  setIO("curcubeu");
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n;
  scanf("%d", &n);
  vector<int> A(n - 1), B(n - 1), C(n - 1);
  scanf("%d %d %d", &A[0], &B[0], &C[0]);
  for(int i = 1; i + 1 < n; i++){
    A[i] = (1ll * A[i - 1] * (i + 1)) % n;
    B[i] = (1ll * B[i - 1] * (i + 1)) % n;
    C[i] = (1ll * C[i - 1] * (i + 1)) % n;
  }
  solve(n, A, B, C);
  return 0;
}