Cod sursa(job #2626204)

Utilizator Gabriela_4Gabriela Ion Gabriela_4 Data 6 iunie 2020 12:31:22
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream in("order.in");
ofstream out("order.out");

int n;
int arbInt[400001];
int pozSiNrCaut;
int nrCopii;

void creeareArbore(int pozNod, int st, int dr) {
    if (st == dr) {
        arbInt[pozNod] = 1;
        return;
    }
    int mijloc = (st + dr) / 2;
    creeareArbore(pozNod * 2, st, mijloc);
    creeareArbore(pozNod * 2 + 1, mijloc + 1, dr);
    arbInt[pozNod] = arbInt[pozNod * 2] + arbInt[pozNod * 2 + 1];
}

void cautareElement(int pozNod, int st, int dr) {
    if (st == dr) {
        out << st << ' ';
        arbInt[pozNod] = 0;
        return;
    }
    int mijloc = (st + dr) / 2;
    if (pozSiNrCaut <= arbInt[pozNod * 2])
        cautareElement(pozNod * 2, st, mijloc);
    else {
        pozSiNrCaut = pozSiNrCaut - arbInt[pozNod * 2];
        cautareElement(pozNod * 2 + 1, mijloc + 1, dr);
    }
    arbInt[pozNod] = arbInt[pozNod * 2] + arbInt[pozNod * 2 + 1];
}


int main() {
    in >> n;
    creeareArbore(1, 1, n);
    pozSiNrCaut = 1;
    nrCopii = n;
    int aux = 1;
    for (int i = 1; i <= n; i++) {
        aux = aux + i;
        if (i != 1)
            aux--;
        if (aux > nrCopii)
            aux %= nrCopii;
        if (aux == 0)
            aux = nrCopii;
        if (i == n)
            aux = 1;
        pozSiNrCaut = aux;
        cautareElement(1, 1, n);
        nrCopii = arbInt[1];
    }
    return 0;
}