Cod sursa(job #1274845)

Utilizator costyv87Vlad Costin costyv87 Data 24 noiembrie 2014 13:55:34
Problema Statistici de ordine Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <cstdio>
#include <stdlib.h>
#include <algorithm>
#include <time.h>
#define ll (long long)
using namespace std;
FILE *f,*g;
int n,k,Q,X,Y,Z,i;
int v[1000100];
long long res;




int partitie(int st, int dr)
{
    int  x=v[(rand()%(dr-st+1))+st];
    int j=dr+1,i=st-1;

    while (1)
    {
       do j--; while (v[j]<x);
       do i++; while (v[i]>x);
       if (i<j)
            swap(v[i],v[j]);
        else
            return j;
    }
}

int divide(int st, int dr,int k)
{
    if (st==dr) return v[st];
    int q;
    q=partitie(st,dr);

    if (k<=q)
        return (divide(st,q,k));
    else
        return (divide(q+1,dr,k));
}


void stat(int st,int dr,int k)
{
    if (st==dr) return ;
    int l=st,r=dr,m = (rand()%(dr-st+1)) + st;
    int val = v[m];


    while (l<=r)
    {
        while ( v[r] < val) r--;
        while ( v[l] > val) l++;

        if (l<=r)
        {
            swap(v[l],v[r]);
            l++; r--;
        }
    }

    l = r;
   // if (l-st+1 == k) return ;
    if (l-st+1 < k)
        stat(l+1,dr,k-(l-st+1));
    else
        stat(st,l-1,k);
}

int main()
{
    f=fopen("beri.in","r");
    g=fopen("beri.out","w");

    srand(time(NULL));

    fscanf(f,"%d%d",&n,&k);
    fscanf(f,"%d%d%d%d",&Q,&X,&Y,&Z);
    for (i=2,v[1]=Q;i<=n;i++)
        v[i] =ll( ll v[i-1] * X + ll Y ) % ll Z +ll k;

    stat(1,n,k);

    for (i=1;i<=k;i++)
        res=ll res+ll (ll v[i]-i+1);

    fprintf(g,"%lld",res);

    return 0;
}