Cod sursa(job #36850)

Utilizator flo_demonBunau Florin flo_demon Data 24 martie 2007 10:58:27
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <stdio.h>

#define MAX 2000007

using namespace std;

long long n, m, L, S, X, Y, Z, V;
long long d[MAX], t[MAX];
long long aux[MAX], pivot, v_aux;
long long countt;

void quickSort(int st, int dr);

int main()
{
    FILE *fin = fopen("toys.in", "r");
    fscanf(fin, "%lld%lld%lld", &n, &L, &m);
    fscanf(fin, "%lld%lld%lld%lld%lld", &S, &X, &Y, &Z, &V);
    d[1] = S;
    t[1] = 1;
    for (long long i = 2; i <= n; ++i)
    {
        d[i] = (X * d[i-1] + Y * (i-1)) % (L - 1) + 1;
        t[i] = (Z * d[i-1] + V * (i-1)) % 2; 
    }
    
    for (long long i = 1; i <= n; ++i)
    {
        if (t[i] == 1)
        {
            aux[i] = d[i];
            countt++;
        }
        else
            aux[i] = (2*L - d[i]); 
    }
    
    quickSort(1, n);
    aux[0] = 0;
    
    long long rez = (m / n) * (2 * L);
    rez += aux[countt];
    FILE *fout = fopen("toys.out", "w");
    fprintf(fout, "%lld\n", rez);
    fclose(fout);
    
    return 0;
}

void quickSort(int st, int dr)
{
    long long i = st - 1, j = dr + 1;
    pivot = aux[st];
    do
    {
        do { i++; } while (pivot > aux[i]);
        do { j--; } while (pivot < aux[j]);
        if (i <= j)
        {
            v_aux = aux[i];
            aux[i] = aux[j];
            aux[j] = v_aux;
        }
    } while (i <= j);
    
    if (i < dr) quickSort(i, dr);
    if (j > st) quickSort(st, j);
}