Cod sursa(job #2901867)

Utilizator DafinaTrufasTrufas Dafina DafinaTrufas Data 14 mai 2022 17:33:55
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <iostream>
#include <fstream>
using namespace std;

int a[30000], d[120000];

ifstream f("order.in");
ofstream g("order.out");

void creare(int nod, int st, int dr)
{
    if(st == dr)
    {
        d[nod] = a[st];
        return;
    }
    creare(nod * 2, st, (st + dr) / 2);
    creare(nod * 2 + 1, (st + dr) / 2 + 1, dr);
    d[nod] = d[nod * 2] + d[nod * 2 + 1];
}

void modif(int nod, int st, int dr, int i, int val)
{
    if(i < st || i > dr) return;
    if(st == dr)
    {
        d[nod] = val;
        return;
    }
    modif(nod * 2, st, (st + dr) / 2, i, val);
    modif(nod * 2 + 1, (st + dr) / 2 + 1, dr, i, val);
    d[nod] = d[nod * 2] + d[nod * 2 + 1];
}

int fixare_poz(int nod, int st, int dr, int poz_interm)
{
    if(st == dr)
    {
        g << st << ' ';
        return st;
    }
    if(d[2*nod] < poz_interm)
        return fixare_poz(nod * 2 + 1, (st + dr) / 2 + 1, dr, poz_interm - d[nod * 2]);
    // daca pozitia copilului care e la rand nu depaseste numarul de copii ramasi in joc din intervalul
    // reprezentat de fiul stang, ii caut pozitia initiala in intervalul din fiul drept
    return fixare_poz(nod * 2, st, (st + dr) / 2, poz_interm);
}

int main()
{int n, i, p, c = 2, nr;
f >> n;
nr = n;
for(i = 1; i <= n; i++)
    a[i] = 1;
creare(1, 1, n);
for(i = 1; i <= n; i++)
{
    c = (i + c - 1) % nr; // pozitia copilului care e la rand, relativ la numarul de copii ramasi in joc
    if(c == 0) c = nr;
    nr--; // actualizez numarul de copii ramasi in joc
    p = fixare_poz(1, 1, n, c);
    modif(1, 1, n, p, 0);
}
f.close();
g.close();
return 0;
}