Cod sursa(job #2904469)

Utilizator NicuDirvaDirva Nicolae NicuDirva Data 17 mai 2022 23:43:01
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <iostream>
#include <fstream>
using namespace std;

int v[30000], d[120000];

ifstream fin("order.in");
ofstream fout("order.out");

void creare(int nod, int st, int dr)
{
    if(st == dr)
    {
        d[nod] = v[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];
}

int fixare(int nod, int st, int dr, int p)
{
    if(st == dr)
    {
        fout<< st << ' ';
        return st;
    }
    if(d[2*nod] < p)
        return fixare(nod * 2 + 1, (st + dr) / 2 + 1, dr, p - d[nod * 2]);

    return fixare(nod * 2, st, (st + dr) / 2, p);
}

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

int main()
{

int n, p, c = 2, nr;

fin >> n;
nr = n;
for(int i = 1; i <= n; i++)
    v[i] = 1;

creare(1, 1, n);

for(int i = 1; i <= n; i++)
{
    c = (i + c - 1) % nr;
    if(c == 0) c = nr;
    nr--;
    p = fixare(1, 1, n, c);
    modificare(1, 1, n, p, 0);
}
return 0;
}