Cod sursa(job #3169131)

Utilizator PescarusTanislav Luca Andrei Pescarus Data 14 noiembrie 2023 11:45:20
Problema Curcubeu Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.2 kb
// #include <fstream>
// using namespace std;

// ifstream f("curcubeu.in");
// ofstream g("curcubeu.out");

// const int nmax = 1000005;
// int n, a, b, c;
// int st[nmax], dr[nmax], C[nmax];
// int Next[nmax]; // vectorul de elemente pe care il sarim cand facem solorarile invers
// int sol[nmax];


// int find_next(int pos){
//     int aux = pos;
//     while(Next[pos] != pos){
//         pos = Next[pos];
//     }
//     int res = pos;
//     pos = aux;
//     while(Next[pos] != res){
//         aux = Next[pos];
//         Next[pos] = res;
//         pos = aux;
//     }
//     return res;
// }
// int main(){
//      f >> n >> a >> b >> c;
//      st[1] = a;
//      dr[1] = b;
//      C[1] = c;
//      for(int i = 2; i <= n - 1; i++){
//         st[i] = (st[i - 1] * i) % n;
//         dr[i] = (dr[i - 1] * i) % n;
//         C[i] = (C[i - 1] * i) % n;
//      }
//     for(int i = 1; i <= n; i++){
//         Next[i] = i;
//     }
//     Next[n] = 0;
//     for(int i = n - 1; i >= 1; i--){
//         for(int j = find_next(st[i]); j <= dr[i]; j = Next[j]){
//             sol[j] = C[i];
//             Next[j] = find_next(j + 1);
//         }
//     }
//     for(int i = 1; i <= n - 1; i++){
//         g << sol[i] << '\n';
//     }
// }

#include <fstream>

using namespace std;
ifstream f("curcubeu.in");
ofstream g("curcubeu.out");
const int nmax = 1000005;


int Next[nmax];
int st[nmax], dr[nmax], sol[nmax], c[nmax];
int n;

int main(){
    f >> n >> st[1] >> dr[1] >> c[1];
    Next[1] = 1;
    for(int i = 2; i <= n - 1; i++){
        Next[i] = i;
        st[i] = (st[i - 1] * i) % n;
        dr[i] = (dr[i - 1] * i) % n;
        c[i] = (c[i - 1] * i) % n;
    }
    Next[n] = 0;
    for(int i = n - 1; i >= 1; i--){
        int stanga = min(st[i], dr[i]);
        int dreapta = max(st[i], dr[i]);
        for(int j = stanga; j <= dreapta && j < n;){
            if(sol[j] == 0){
                sol[j] = c[i];
                Next[j] = dreapta + 1;
                j++;
            }
            else{
                j = Next[j];
            }
        }

    }
    for(int i = 1; i < n; i++){
        g << sol[i] << '\n';
    }
}