Cod sursa(job #3319784)

Utilizator horia.boeriuBoeriu Horia Andrei horia.boeriu Data 3 noiembrie 2025 11:29:17
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <iostream>

using namespace std;
const int MAXN = 30000;
int aib[MAXN + 1];
int n2;
void addBit(int poz, int val) {
    while (poz <= n2) {
        aib[poz] += val;
        poz += (poz & (-poz));
    }
}
int bitSum(int poz) {
    int s;
    s = 0;
    while (poz > 0) {
        s += aib[poz];
        poz &= (poz - 1);
    }
    return s;
}
int main()
{
    //cod neterminat
    int i;
    fin = fopen("order.in", "r");
    fscanf(fin, "%d", &n);
    fclose(fin);
    n2 = 2 * n;
    for (i = 1; i <= n; i++) {
        addBit(i, 1);//inca e in sir
        addBit(n + i, 1);//inca e in sir
    }
    p2 = 1;
    while ((1 << p2) <= n) {
        p2++;
    }
    p2--;
    fout = fopen("order.out", "w");
    poz = 2;
    for (i = 1; i <= n; i++) {
        //o caut binar pe a i-a pozitie activa incepand de la i
        x = i % (n - i + 1);

        //fac cb pe aib in care scad prefixul
        //dublez vectorul
        val = bitSum(poz - 1);
        poz = s = 0;
        for (p = p2; p >= 0; p--) {
            if (poz + (1 << p) <= n2 && s + aib[poz + (1 << p)] - val < i) {
                s += aib[poz + (1 << p)];
                poz += (1 << p);
            }
        }
        poz++;
    }
    fprintf(fout, "\n");
    fclose(fout);
    return 0;
}