Cod sursa(job #854330)

Utilizator maritimCristian Lambru maritim Data 13 ianuarie 2013 12:59:12
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<stdio.h>
#include<math.h>

FILE *f = fopen("order.in","r");
FILE *g = fopen("order.out","w");

#define MaxN 30100
#define MaxSQRT 200

int N,sq;
int A[MaxN],SQRT[MaxN];

void citire(void)
{
    fscanf(f,"%d",&N);
}

void build(void)
{
    sq = sqrt(N);

    for(int i=1;i<=N;i++)
        A[i] = 1,
        SQRT[i/sq+1] ++;
}

inline void update(int p)
{
    A[p] = 0;

    SQRT[p/sq+1] --;
}

inline int querry(int val)
{
    int sqp,sum = 0;

    for(sqp = 0;sum<val;sum += SQRT[++sqp]);

    sum -= SQRT[sqp--];
    sqp *= sq;
    
    for( sqp ? --sqp : 0;sum < val; sum += A[++sqp]);

    return sqp;
}

void Rezolvare(void)
{
    int nr = N,poz,a = 2;

    build();

    for(int i=1;i<=N;i++)
    {
        a = (a - 1 + i) % nr;
        !a ? a = nr : 0;
        
        poz = querry(a);
        update(poz);
        fprintf(g,"%d ", poz);

        -- nr;
    }
}

int main()
{
    citire();
    Rezolvare();
}