Cod sursa(job #1880030)

Utilizator Dan_RadulescuRadulescu Dan Dan_Radulescu Data 15 februarie 2017 12:59:14
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include<stdio.h>
#include<stdlib.h>
using namespace std;

FILE *f1 = fopen("order.in", "r");
FILE *f2 = fopen("order.out", "w");

int n, i, nr_copil;
struct nod
{
    int nrf, copil;
}arb[100000];

void creare(int node, int st, int dr)
{
    int mij;
    if (st == dr)
    {
        arb[node].nrf = 1;
        arb[node].copil = st;
        return;
    }
    mij = (st + dr) / 2;
    creare(2*node, st, mij);
    creare(2*node+1, mij + 1, dr);
    arb[node].nrf = arb[2*node].nrf + arb[2*node+1].nrf;
}

void elimina(int node, int &res, int nr, int st, int dr)
{
    int mij;
    arb[node].nrf--;
    if (st == dr)
    {
        res = arb[node].copil;
        return;
    }

    mij = (st + dr) / 2;

    if (nr <= arb[2*node].nrf)
        elimina(2*node, res, nr, st, mij);
    else elimina(2*node+1, res, nr - arb[2*node].nrf, mij + 1, dr);
}

int main()
{
    fscanf(f1, "%d", &n);
    fclose(f1);
    nr_copil = 1;
    int res;
    creare(1, 1, n);
    for (i = 1; i <= n; i++)
    {
        nr_copil = nr_copil + i;
        nr_copil = nr_copil % arb[1].nrf;
        if (nr_copil == 0) nr_copil = arb[1].nrf;
        elimina(1, res, nr_copil, 1, n);
        fprintf(f2, "%d ", res);
        nr_copil--;
    }
    fclose(f2);
    return 0;
}