Cod sursa(job #2774596)

Utilizator racsosabeVictor Racso Galvan Oyola racsosabe Data 12 septembrie 2021 02:27:12
Problema Curcubeu Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 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;
  for(int i = 0; i < n - 1; i++){
    while(pos_use < use.size() and A[use[pos_use]] <= i){
      times.emplace(use[pos_use]);
      pos_use++;
    }
    while(pos_take < take.size() and B[take[pos_take]] <= i){
      times.erase(take[pos_take]);
      pos_take++;
    }
    if(times.empty()) continue;
    res[i] = C[*times.rbegin()];
  }
  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;
}