Cod sursa(job #2774607)

Utilizator racsosabeVictor Racso Galvan Oyola racsosabe Data 12 septembrie 2021 03:06:37
Problema Curcubeu Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.86 kb
#pragma optimize ("unroll-loops")
#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);
}
 
vector<int> sort(vector<int> &v){
  vector<int> head(v.size() + 1, 0);
  for(int x : v) head[x]++;
  int sum = 0;
  for(int i = 0; i < head.size(); i++){
    sum += head[i];
    head[i] = sum - head[i];
  }
  vector<int> p(v.size());
  for(int i = 0; i < v.size(); i++){
    p[head[v[i]]++] = i;
  }
  return p;
}
 
void solve(int n, vector<int> &A, vector<int> &B, vector<int> &C){
  for(int i = 0; i + 1 < n; i++){
    if(A[i] > B[i]) swap(A[i], B[i]);
    A[i]--;
  }
  vector<int> use = sort(A), take = sort(B);
  set<int> times;
  vector<int> res(n - 1, 0);
  int pos_use = 0, pos_take = 0;
  vector<bool> vis(n - 1, false);
  int at = 0;
  for(int i = 0; i < n - 1; i++){
    while(pos_use < use.size() and A[use[pos_use]] <= i){
      vis[use[pos_use]] = true;
      at = max(at, use[pos_use]);
      pos_use++;
    }
    while(pos_take < take.size() and B[take[pos_take]] <= i){
      vis[take[pos_take]] = false;
      pos_take++;
    }
    while(at >= 0 and !vis[at]) at--;
    if(at == -1) continue;
    res[i] = C[at];
  }
  for(int i = 0; i + 1 < 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;
}